문제
예선전에서 승리한 삼성이는 결승전 까지 진출하게 되었다.
결승전인 만큼 수영장이 아닌 바다에서 진행되었다.
바다 전체를 사용 할 수 없기에 가로 N 세로 N만큼의 공간만 사용하여 진행하도록 하였다.
이 공간을 벗어나면 실격처리가 되므로 공간안에서 가장 빠른 길을 찾아야 한다.
이 공간에는 섬과 같은 지나갈 수 없는 장애물과, 주기적으로 사라졌다 나타나는 소용돌이 같은 장애물이 존재한다.
( 섬과 같은 장애물은 지도에서 1로 표시, 소용돌이 같은 장애물은 2로 표시 )
소용돌이는 생성되고 2초동안 유지되다가 1초동안 잠잠해진다.
예를들어, 0초에 생성된 소용돌이는 0초, 1초까지 유지되고 2초에 사라지게된다. 또한 3초, 4초에는 생성되고 5초에 사라진다.
(단 ,한번 통과한 소용돌이 위에서는 머물러 있을 수 있다 )
이런 바다에서 삼성이를 우승시키려면 어떤 경로로 보내야 될까?
똑똑한 여러분들은 한번에 그 경로를 찾을 수 있었다. 해당 경로로 수영을 했을때 삼성이는 몇초만에 골인 할 수 있을까?
5 //N
0 0 0 0 0
0 0 0 1 0
0 0 0 1 0
2 2 1 1 0
0 0 0 0 0
4 0 //시작점
2 0 //도착점
EX)
이 경우에는 (4,0) 에서 시작, 소용돌이가 존재하므로 이동하지 않는다 ( 0초 )
(4,0) 아직 소용돌이가 사라지지 않았으므로 제자리에 있다 ( 1초)
(4,0) 이제 소용돌이가 사라지는 것을 보았고 건너려고한다 ( 2초)
(3,0) 소용돌이를 통과하였고 바다위를 수영하고 있다 (3초)
(2,0) 도착지에 도착하였다 (4초)
입력
첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 수영장의 크기 N ( 2<=N<=15 )
다음 N개의 줄의 i번째 줄에는 수영장의 모양이 공백으로 구분되어 주어진다. ( 0 : 지나갈 수 있는 곳 , 1 : 장애물 , 2: 주기가 2초인 소용돌이)
다음으로 시작위치 A,B가 주어지고 ( 0<=A,B<=N-1)
마지막 줄에 도착위치 C, D가 주어진다 ( 0 <=C,D<=N-1) ( 도착점과 시작점은 소용돌이가 아니다 )
출력
각 테스트 케이스마다 테스트 케이스의 번호와 이동시간을 공백을 두고 표시한다
도착 할 수 없다면 -1을 출력한다.
(Ex) #1 4
풀이
BFS를 기반으로 몇 가지 조건을 추가하였다.
- 소용돌이의 경우 2초동안 발생하고 1초동안 사라진다.
- 즉, 시간을 기점으로 (Time % 3 == 2)일 경우 길이 생기게 된다. 이 경우 이동할 수 있게 된다.
- 따라서 기존의 4방탐색과 달리, '기다린다'는 선택지를 추가해야 했다. 그렇기에 이동 배열에
{0, 0}을 추가하였다. - 하지만 무한정 기다리는 것은 스택 오버플로우 에러가 나기 때문에, 제자리에서 기다린 시간인
stay변수를 큐에 추가로 넘겨주기로 하였다.
해당 옵션을 추가하여 풀이한 코드는 하단과 같다. 자세한 내용은 주석에 첨부하였다.
코드
/*
1. 소용돌이는 2초 생성 후 1초 사라짐
ex) 0 1 유지 2 삭제 3 4 유지 ..
2. time % 3 == 2일 경우 움직일 수 있게 조건을 달 수도 있을 것 같음.
3. 기존의 BFS와는 달리 제자리에서 유지한다는 조건이 필요할 것 같음. 단, 제자리에서 3초 이상 유지하는 것은 배제함. (StackOverFlow방지)
*/
public class SWEA_4193_수영대회결승전 {
static int pos[][] = new int[2][2]; //시작지점과 종료 지점을 담을 배열
static int[][] shift = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}, {0, 0}}; //5방 탐색
static Queue<int[]> q = new ArrayDeque<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
int cnt = 0;
//TestCase 반복
while(cnt++ < T) {
int N = Integer.parseInt(br.readLine());
int[][] map = new int[N][N];
//맵 입력받기
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
//위치 입력받기
for (int i = 0; i < 2; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < 2; j++) {
pos[i][j] = Integer.parseInt(st.nextToken());
}
}
//출력
System.out.println("#" + cnt + " " + solve(map));
}
}
private static int solve(int[][] map) {
//pos[0] = 시작지, pos[1] = 도착지
int res = Integer.MAX_VALUE; //결과
int size = map.length; //맵 크기
boolean visit[][] = new boolean[size][size]; //방문 체크
q.offer(new int[] {pos[0][0], pos[0][1], 0, 0}); //r, c, 시간, 제자리 시간 측정
while(!q.isEmpty()) {
int[] temp = q.poll();
int r = temp[0];
int c = temp[1];
int time = temp[2];
int stay = temp[3];
//방문 처리
visit[r][c] = true;
//최저값 갱신 : 목적지 도착
if(r == pos[1][0] && c == pos[1][1]) {
res = Math.min(res, time);
continue;
}
for (int i = 0; i < shift.length; i++) {
int nr = r + shift[i][0];
int nc = c + shift[i][1];
if(nr < 0 || nc < 0 || nr >= size || nc >= size) continue; //인덱스 아웃 방지
if(map[nr][nc] == 1) continue; //1. 장애물
if(i != 4 && map[nr][nc] == 2 && time % 3 != 2) continue; //2. 갈 수 없는 소용돌이일 경우 스킵
if(i != 4 && visit[nr][nc]) continue; //3. 제자리 이동을 제외한 방문 처리인 경우 스킵
if(stay == 3) continue; //4. 제자리 이동을 3초 이상 하였을 경우 스킵
//======= 여기까지 탈락 조건 ======//
//제자리 이동 인덱스일 경우 시간 추가, 아닐 경우 시간 초기화
if(i == 4) q.offer(new int[] {nr, nc, time + 1, stay + 1});
else q.offer(new int[] {nr, nc, time + 1, 0});
}
}
//결과 출력
if(res == Integer.MAX_VALUE) return -1;
return res;
}
}
