[swea-D4] 4193. 수영대회 결승전 ( 완전 탐색 + 구현 )

[swea-D4] 4193. 수영대회 결승전 ( 완전 탐색 + 구현 )

문제

예선전에서 승리한 삼성이는 결승전 까지 진출하게 되었다.

결승전인 만큼 수영장이 아닌 바다에서 진행되었다.

바다 전체를 사용 할 수 없기에 가로 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을 출력한다.

입력

3
5
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
6
0 0 0 0 0 0
0 1 1 0 0 0
0 0 0 1 2 0
1 1 0 1 0 1
0 0 0 1 0 1
0 0 0 2 0 1
5 0
2 5
6
0 0 0 0 0 0
0 0 0 0 0 0
1 0 1 1 1 0
1 0 0 0 0 0
1 0 1 1 1 0
0 0 2 0 2 0
5 0
3 5

출력

#1 4
#2 10
#3 7

🙋‍♂️ 들어가며

• 소용돌이에 들어왔으면 머무를 수 있음
• 도달못하면 -1
• 시간은 2초, 5초, 8초 마다 소용돌이를 지나가기 가능

✅ 코드

import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;


import java.util.LinkedList;
import java.util.Queue;


public class Solution {
	static int[] dr = {-1,1,0,0};
	static int[] dc = {0,0,-1,1};
	
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		
		for (int tc = 1; tc < T+1; tc++) {
			int N = Integer.parseInt(br.readLine());
			int[][] arr = new int[N][N];
			for (int r = 0; r < N; r++) {
				String[] cols = br.readLine().split(" ");
				for (int c = 0; c < cols.length; c++) {
					arr[r][c] = Integer.parseInt(cols[c]);
				}
			}
			String[] sr_sc = br.readLine().split(" ");
			String[] er_ec = br.readLine().split(" ");
			int sr = Integer.parseInt(sr_sc[0]);
			int sc = Integer.parseInt(sr_sc[1]);
			int er = Integer.parseInt(er_ec[0]);
			int ec = Integer.parseInt(er_ec[1]);
			
			// 1. 최단거리 탐색 시작
			int min_dist = bfs(N, arr, sr, sc, er, ec);
			
			// 3. 출력
			System.out.println("#" + tc + " " + min_dist);
		}
	}
	
	
	// 2. 함수 (bfs)
	static int bfs(int N, int[][] arr, int sr, int sc, int er, int ec) {
		
		// 2-0. 갔던 장소 되돌아가지않기 위해 시간초과방지.
		boolean[][] visited = new boolean[N][N];
		
		// 2-1. Q생성후 시작좌표 삽입
		Queue<int[]> q = new LinkedList<>();
		int s_dist = 0;
		q.add(new int[] {sr, sc, s_dist});
		visited[sr][sc] = true;
		
		// 2-2. 도착점까지 탐색
		while (!q.isEmpty()) {
			int[] cur = q.poll();
			int cr = cur[0];
			int cc = cur[1];
			int c_dist = cur[2];
			
			// 2-3. 만약 목적지 도달시
			if (cr == er && cc == ec) {
				return c_dist;
			}
			
			// 2-4. 목적지 도달 못했다면
			for (int d = 0; d < 4; d++) {
				int nr = cr + dr[d];
				int nc = cc + dc[d];
				
				// 2-5. 만약 범위 밖 -> skip
				if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
				
				// 2-6. 범위안이지만 장애물이면 -> skip
				if (arr[nr][nc] == 1) continue;
				
				// 2-7. 만약 다음 좌표가 소용돌이면 -> 제자리 대기 -> 다음으로
				if (arr[nr][nc] == 2) {
					int n_dist = c_dist + 1;
					
					// 2-7-a. 만약 못지나가면 제자리 대기
					if (c_dist % 3 != 2) {
						q.add(new int[] {cr, cc, n_dist});
					}
					// 2-7-b. 그렇지않고, 소용돌이가 잠잠해져서 지나갈 수 있다면?
					else if (c_dist % 3 == 2) {
						q.add(new int[] {nr, nc, n_dist});
					}
					continue;
				}

				
				// 2-8. 방문했으면? -> 다음으로
				if (visited[nr][nc]) continue;
				
				// 2-8. 범위안이고, 장애물도 아니고, 방문도 안했으면?
				visited[nr][nc] = true;
				int n_dist = c_dist+1;
				q.add(new int[] {nr, nc, n_dist});
			}
		}
		return -1;
		
	}
	
	
	
	
}