[SWEA] 모의 SW 역량테스트 1953번 탈주범 검거 (JAVA)

문제 출처 - SW Expert Academy

문제는 여기

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 개 이다.

 

지하 터널 지도와 맨홀 뚜껑의 위치, 경과된 시간이 주

어질 때 탈주범이 위치할 수 있는 장소의 개수를 계산하는 프로그램을 작성하라.

[입력]

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

[출력]

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

 

 

---

[풀이]

1. BFS를 통해 완전 탐색을 한다.

2. 입력받은 l(시간)에서 1을 빼준다. (맨홀 뚜껑을 통해 들어가는데 1시간이 걸린다.)

3. BFS 탐색을 하면서 다음 칸이 파이프가 연결이 되어있는 경우에만 탐색을 진행한다.

[접근]

1. 완전 탐색 중 BFS와 DFS 어느 것을 선택할지 고민했다.

2. BFS로 접근하는 방법이 더 쉬울 것 같아 BFS를 선택했다.

3. 맨홀의 모양에 따라 이동할 수 있는 방향을 담은 배열을 2차원으로 만들어 준다.

4. 현재 파이프에서 이동을 할 수 있을 경우의 다음 파이프의 모양을 담은 배열을 만들어준다.

5. BFS 탐색을 진행한다.

[코드]

package swet;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Solution_test_1953_김재욱 {
	static int T;
	static int n; // 세로 크기
	static int m; // 가로 크기
	static int r; // 맨홀 세로 위치
	static int c; // 맨홀 가로 위치
	static int l; // 탈출에 소요된 시간
	static int map[][]; // 파이프 상태를 받을 배열
	static boolean[][] visited; // 방문처리용 배열
	static int count; // 있을 수 있는 곳의 개수

	// 1~7 모양의 델타 배열
	static int[][] dr = {{-1, 1, 0, 0}, {-1, 1, 0, 0}, {0, 0, 0, 0}, {-1, 0, 0, 0}, {0, 1, 0, 0}, {0, 1, 0, 0}, {-1, 0, 0, 0}};
	static int[][] dc = {{0, 0, -1, 1}, {0, 0, 0, 0}, {0, 0, -1, 1}, {0, 0, 0, 1}, {0, 0, 0, 1}, {0, 0, -1, 0}, {0, 0, -1, 0}};
	// 다음 위치의 파이프가 해당 모양일 때 이동가능함을 담은 배열
	static int[][] next = {{1, 2, 5, 6}, {1, 2, 4, 7}, {1, 3, 4, 5}, {1, 3, 6, 7}};

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		T = Integer.parseInt(br.readLine());

		for (int t = 1; t <= T; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());

			n = Integer.parseInt(st.nextToken());
			m = Integer.parseInt(st.nextToken());
			r = Integer.parseInt(st.nextToken());
			c = Integer.parseInt(st.nextToken());
			l = Integer.parseInt(st.nextToken()) - 1; // 1시간이 되어야 맨홀 안으로 들어가니까 1을 빼준다.

			// 초기화 해주기
			map = new int[n][m];
			visited = new boolean[n][m];
			count = 1; // 맨홀 구멍으로 들어간다고 하면 들어간 상태일 때 해당 자리를 포함해야 하니까

			// 입력받기
			for (int i = 0; i < n; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < m; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
				}
			}

			bfs(r, c);

			System.out.println("#" + t + " " + count);
		}
	}

	public static void bfs(int x, int y) {
		Queue<int[]> q = new LinkedList<>();
		visited[x][y] = true;
		q.add(new int[] {x, y, 0});
		// x, y, 시간

		while(!q.isEmpty()) {
			int[] cur = q.poll();
			int delta = map[cur[0]][cur[1]] - 1; // 현재 좌표의 파이프
			
			if(cur[2] == l) { // 시간이 주어진 시간과 동일해지면 종료
				return;
			}

			for(int i = 0; i < 4; i++) {
				int nr = cur[0] + dr[delta][i];
				int nc = cur[1] + dc[delta][i];

				if (cur[0] == nr && cur[1] == nc) // 이동을 했는데 그게 현재 위치라면 탐색 불가
					continue;

				if (nr >= 0 && nc >= 0 && nr < n && nc < m && map[nr][nc] != 0) {
					// 범위안에 들어있고 0이 아닌 곳(파이프가 아니면 이동 불가)
					for (int j = 0; j < 4; j++) {
						if (next[i][j] == map[nr][nc]) {
							// 다음 지점이 갈수 있는 곳인지(가려고 해도 파이프가 연결되지 않은 모양이라면 못가니까)
							if (!visited[nr][nc]){ // 방문하지 않은 곳이라면 
								visited[nr][nc] = true; // 방문처리하고
								count++; // 횟수 증가
								q.add(new int[] {nr, nc, cur[2] + 1});
								// 다음 위치와 증가한 시간
							}
						}
					}
				}
			}
		}
	}
}

[실수]

1. dr 배열과 dc배열 안의 배열들의 크기를 다르게 줘서 처리를 할 때 문제가 발생했다. 이를 해결하기 위해 이동을 안 하는 곳이지만 0,0을 넣어 4칸을 맞춰서 해결시켰다.

2. 다음 파이프의 모양을 생각하지 않고 탐색을 하여 값에 오류가 발생했다.