[SWEA] 1953번 탈주범 검거 - 자바(JAVA) / 시뮬레이션/ BFS

📑 문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq& 

SW Expert Academy

교도소로 이송 중이던 흉악범이 탈출하는 사건이 발생하여 수색에 나섰다.
탈주범은 탈출한 지 한 시간 뒤, 맨홀 뚜껑을 통해 지하터널의 어느 한 지점으로 들어갔으며,
지하 터널 어딘가에서 은신 중인 것으로 추정된다.

터널끼리 연결이 되어 있는 경우 이동이 가능하므로 탈주범이 있을 수 있는 위치의 개수를 계산하여야 한다.
탈주범은 시간당 1의 거리를 움직일 수 있다.
지하 터널은 총 7 종류의 터널 구조물로 구성되어 있으며 각 구조물 별 설명은 [표 1]과 같다.

 

 

[그림 1-1] 은 지하 터널 지도의 한 예를 나타낸다.

이 경우 지도의 세로 크기는 5, 가로 크기는 6 이다.
맨홀 뚜껑의 위치가 ( 2, 1 ) 으로 주어질 경우, 이는 세로 위치 2, 가로 위치 1을 의미하며 [그림 1-2] 에서 붉은 색으로 표기된 구역이다.
탈주범이 탈출 한 시간 뒤 도달할 수 있는 지점은 한 곳이다.
탈주범이 2시간 후 도달할 수 있는 지점은, [그림 1-3] 과 같이 맨홀 뚜껑이 위치한 붉은 색으로 표시된 지하도 와 파란색으로 표기된 지하도까지 총 3개의 장소에 있을 수 있다.
3시간 후에는 [그림 1-4] 과 같이 총 5개의 지점에 있을 수 있다.

 

 

 

[그림 2-1] 에서 맨홀뚜껑이 위치한 지점이 ( 2, 2 ) 이고 경과한 시간이 6 으로 주어질 경우,
[그림 2-2] 에서 맨홀뚜껑이 위치한 지점은 붉은 색, 탈주범이 있을 수 있는 장소가 푸른색으로 표기되어 있다.
탈주범이 있을 수 있는 장소는, 맨홀뚜껑이 위치한 지점을 포함하여 총 15 개 이다.

 

 

지하 터널 지도와 맨홀 뚜껑의 위치, 경과된 시간이 주어질 때 탈주범이 위치할 수 있는 장소의 개수를 계산하는 프로그램을 작성하라.


[제약 사항]
1. 시간 제한 : 최대 50개 테이트 케이스를 모두 통과하는데, C/C++/Java 모두 1초
2. 지하 터널 지도의 세로 크기 N, 가로 크기 M은 각각 5 이상 50 이하이다. (5 ≤ N, M ≤ 50)
3. 맨홀 뚜껑의 세로 위치 R 은 0 이상 N-1이하이고 가로 위치 C 는 0 이상 M-1이하이다. (0 ≤ R ≤ N-1, 0 ≤ C ≤ M-1)
4. 탈출 후 소요된 시간 L은 1 이상 20 이하이다. (1 ≤ L ≤ 20)
5. 지하 터널 지도에는 반드시 1개 이상의 터널이 있음이 보장된다.
6. 맨홀 뚜껑은 항상 터널이 있는 위치에 존재한다.

[입력]
첫 줄에 총 테스트 케이스의 개수 T가 주어진다.
두 번째 줄부터 T개의 테스트 케이스가 차례대로 주어진다.
각 테스트 케이스의 첫 줄에는 지하 터널 지도의 세로 크기 N, 가로 크기 M, 맨홀 뚜껑이 위치한장소의 세로 위치 R, 가로 위치 C, 그리고 탈출 후 소요된 시간 L 이 주어진다.
그 다음 N 줄에는 지하 터널 지도 정보가 주어지는데, 각 줄마다 M 개의 숫자가 주어진다.
숫자 1 ~ 7은 해당 위치의 터널 구조물 타입을 의미하며 숫자 0 은 터널이 없는 장소를 의미한다.

[출력]
테스트 케이스의 개수만큼 T줄에 T개의 테스트 케이스 각각에 대한 답을 출력한다.
각 줄은 “#x”로 시작하고 공백을 하나 둔 다음 정답을 기록한다. (x는 1부터 시작하는 테스트 케이스의 번호이다)
출력해야 할 정답은 탈주범이 위치할 수 있는 장소의 개수이다.

 

 

 

 

 

 

 

 

 

✒️ 풀이

 ✔️ 파이프 번호마다 이동할 수 있는 모든 방향을 표시한다.

    이때 표시되는 값 x는 현재 위치에서 r+dr[x], c+dc[x]를 표시할 때의 방향 값이다.

 

   예) dr={1, -1, 0, 0} / dc={0,0,1,-1} >> 상하우좌

   방향 값이 0이라면 r+dr[0], c+dc[0]을 통해 위쪽으로 이동하게 된다.

   방향 값이 3이라면 r+dr[3], c+dc[3]이 되면서 좌측으로 이동한다.

 

   즉, 파이프 번호가 2이고 그때 이동할 수 있는 방향 값이 0, 1로 주어진다면,

   이 파이프는 아래(0)/위(1)로 이동할 수 있다는 뜻이 된다.

   나는 아래처럼 표시했다. 방향 값이 -1인 것은 이동할 수 없는 곳이란 뜻이다.

static int[][] tunnel = {		// 파이프 번호
			{-1},		// 0 없는 번호
			{0,1,2,3},	// 1
			{0,1},		// 2
			{2,3},		// 3
			{1,2},		// 4
			{0,2},		// 5
			{0,3},		// 6
			{1,3}		// 7
};

 

 다시 한 번 설명해보겠다.

 5번 파이프가 있다고 해보자. 이 파이프를 만났을 때 이동할 수 있는 방향을 보려면 tunnel 변수의 5번 배열을 보면 된다. 

이동할 수 있는 방향: 하/우

 그림에서 볼 수 있듯이, 현재 5번 파이프 위에 있다고 한다면 이동할 수 있는 방향은 아래쪽(0), 오른쪽(2) 두 가지밖에 없다.

 따라서 tunnel[5]의 값으로는 0,2가 들어가게 된다.

 

 

 

 

 ✔️ 현재 위치에서 사방을 확인, 새로 이동할 수 있는 위치를 대기큐에 넣는다.

    이미 방문처리된 위치라면 다시 보지 않는다.

 

 ✔️ 이동할 수 있는 위치라도 현재 위치와 이어져 있는지를 확인해야한다.

    후보 위치에서 방문할 수 있는 위치를 확인했을 때 현재 위치가 있다면, 후보 위치로 이동할 수 있다. (큐에 넣을 수 있다)

 

 예시로는 다음과 같은 사진을 들 수 있다.

 아래 파이프에서는 위쪽으로 이동할 수 있지만, 위쪽 파이프가 아래 파이프와 연결되어있지 않으므로 이동할 수 있는 조건이 아니다. 이러한 조건을 생각해주어야 한다.

 

 

 ✔️ 큐에 값을 넣을 때는 위치값과 함께 시간도 1을 더해 넣어준다.

    큐에서 새로 뽑은 현재 위치가 소요시간 L일 때에는 다음 위치를 살펴볼 필요가 없다.

 

 

 

 

 

 

 

🙋‍♀️ 의견

 솔직히 내가 짠 코드가 최적의 코드인지는 모르겠다 (ㅎㅎ)

 교수님이 따로 풀이를 해주셨는데, 하필 딱 그때 평소답지 않게 졸아버려서.....코드가 없다.

 다시 정리하려고 보니까 싸피를 퇴소해서 코드를 볼 수가 없네. 

 

 

 

 

 

 

 

 

 

 

💻 소스코드: 자바(Java)

public class Solution_SWEA_1953_탈주범검거_나세이 {

	static int[] dr = {1,-1,0,0};
	static int[] dc = {0,0,1,-1};
	static int[][] tunnel = {
			{-1},		// 0
			{0,1,2,3},	// 1
			{0,1},		// 2
			{2,3},		// 3
			{1,2},		// 4
			{0,2},		// 5
			{0,3},		// 6
			{1,3}		// 7
	};
	static int[][] map;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int TC = Integer.parseInt(br.readLine().trim());
		for (int testCase = 1; testCase <= TC; testCase++) {
			StringTokenizer st = new StringTokenizer(br.readLine().trim());
			int N = Integer.parseInt(st.nextToken());	//세로
			int M = Integer.parseInt(st.nextToken());	//가로
			int R = Integer.parseInt(st.nextToken());	//맨홀R
			int C = Integer.parseInt(st.nextToken());	//맨홀C
			int L = Integer.parseInt(st.nextToken());	//소요시간
			
			map = new int[N][M];
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine().trim());
				for (int j = 0; j < M; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
				}
			}//input
			
			int result = 0;
			boolean[][] visited = new boolean[N][M];
			Queue<int[]> queue = new LinkedList<int[]>();
			queue.offer(new int[] {R,C, 1});	// r, c, time
			visited[R][C]=true;
			result++;
			
			while(queue.size()>0) {
				int[] cur = queue.poll();
				int r = cur[0];
				int c = cur[1];
				int t = cur[2];
				int p = map[r][c];//현재 위치의 파이프 번호
				//소요시간이 다 됐으면 더 움직이지 않는다.
				if(t==L) continue;
				
				// 현재 위치의 파이프에서 이동할 수 있는 모든 방향을 탐색
				for (int i = 0; i < tunnel[p].length; i++) {
					int nd = tunnel[p][i];
					int nr = r + dr[nd];
					int nc = c + dc[nd];
					
					if(nr<0||nc<0||nr>=N||nc>=M||
							map[nr][nc]==0 ||
							visited[nr][nc]) continue;

					// 새 파이프가 현재 위치와 연결되어있지 않다면 패스
					if(!isConnected(r,c,nr,nc)) continue;
                    
					// 탐색한 위치로 이동
					visited[nr][nc]=true;
					queue.offer(new int[] {nr,nc, t+1});
					result++;
				}
			}//
			
			sb.append("#").append(testCase).append(" ").append(result).append("\n");
		}//end of testCase
		System.out.println(sb);
	}//end of main
	
	private static boolean isConnected(int r1, int c1, int r2, int c2) {
		int p = map[r2][c2]; //새 파이프 번호
		for (int i = 0; i < tunnel[p].length; i++) {//새 파이프에서 이동할 수 있는 모든 방향
			int nd = tunnel[p][i];
			//현재 방향으로 연결되어 있다면
			if(r2+dr[nd]==r1 && c2+dc[nd]==c1) {
				return true;
			}
		}
		return false;
	}//end of isConnected
}//end of class

 

 

 

 

 

 

 

 

 

 

 

💎 💎 💎

 

 

Ｐｏｓｔｅｄ Ｂｙ ＳＡＹ

𝘛𝘩𝘢𝘯𝘬𝘴 𝘧𝘰𝘳 𝘳𝘦𝘢𝘥𝘪𝘯𝘨