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

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

 

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

 

 

이 문제를 해결하기 위해서 BFS 완전탐색을 활용했습니다.

 

Queue를 활용을 해서 해당하는 위치에 도착해서 탈주범이 있을 수 있다면 Queue에 넣어서 이동경로를 저장하게 됩니다.

 

이때 Point라는 클래스를 만들어서 x,y 좌표를 저장을 해서 관리할 수 있도록 추가해서 사용했습니다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Solution {
	private static class Point {
		int x, y;

		public Point(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}

	}

	private static int arr[][], N, M;
	private static boolean visited[][];

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int T = Integer.parseInt(st.nextToken());
		for (int t = 1; t <= T; t++) {
			st = new StringTokenizer(br.readLine(), " ");
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			int R = Integer.parseInt(st.nextToken());
			int C = Integer.parseInt(st.nextToken());
			int L = Integer.parseInt(st.nextToken());
			arr = new int[N][M];
			visited = new boolean[N][M];
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				for (int j = 0; j < M; j++) {
					arr[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			LinkedList<Point> que = new LinkedList<>();	// 좌표를 담아줄 리스트
			que.add(new Point(R, C));	// 시작 좌표
			visited[R][C] = true;
			int answer = 0;
			int time = 0;
			while (!que.isEmpty() && time != L) { // 시간이 다되거나 더 이상 경로가 없을때 까지
				int size = que.size();
				for (int i = 0; i < size; i++) {
					Point p = que.poll();
					answer++;
					switch (arr[p.x][p.y]) {	//해당 좌표에 따라 분리
					case 1:
						if (up(p)) {
							que.add(new Point(p.x - 1, p.y));
							visited[p.x - 1][p.y] = true;
						}
						if (down(p)) {
							que.add(new Point(p.x + 1, p.y));
							visited[p.x + 1][p.y] = true;
						}
						if (left(p)) {
							que.add(new Point(p.x, p.y - 1));
							visited[p.x][p.y - 1] = true;
						}
						if (right(p)) {
							que.add(new Point(p.x, p.y + 1));
							visited[p.x][p.y + 1] = true;
						}
						break;
					case 2:
						if (up(p)) {
							que.add(new Point(p.x - 1, p.y));
							visited[p.x - 1][p.y] = true;
						}
						if (down(p)) {
							que.add(new Point(p.x + 1, p.y));
							visited[p.x + 1][p.y] = true;
						}
						break;
					case 3:
						if (left(p)) {
							que.add(new Point(p.x, p.y - 1));
							visited[p.x][p.y - 1] = true;
						}
						if (right(p)) {
							que.add(new Point(p.x, p.y + 1));
							visited[p.x][p.y + 1] = true;
						}
						break;
					case 4:
						if (up(p)) {
							que.add(new Point(p.x - 1, p.y));
							visited[p.x - 1][p.y] = true;
						}
						if (right(p)) {
							que.add(new Point(p.x, p.y + 1));
							visited[p.x][p.y + 1] = true;
						}
						break;
					case 5:
						if (down(p)) {
							que.add(new Point(p.x + 1, p.y));
							visited[p.x + 1][p.y] = true;
						}
						if (right(p)) {
							que.add(new Point(p.x, p.y + 1));
							visited[p.x][p.y + 1] = true;
						}
						break;
					case 6:
						if (down(p)) {
							que.add(new Point(p.x + 1, p.y));
							visited[p.x + 1][p.y] = true;
						}
						if (left(p)) {
							que.add(new Point(p.x, p.y - 1));
							visited[p.x][p.y - 1] = true;
						}
						break;
					case 7:
						if (up(p)) {
							que.add(new Point(p.x - 1, p.y));
							visited[p.x - 1][p.y] = true;
						}
						if (left(p)) {
							que.add(new Point(p.x, p.y - 1));
							visited[p.x][p.y - 1] = true;
						}
						break;
					}
				}
				time++;
			}
			System.out.println("#" + t + " " + answer);
		}
	}

	private static boolean right(Point p) {	//오른쪽 확인
		int x = p.x;
		int y = p.y + 1;
		if (x >= 0 && y >= 0 && x < N && y < M && !visited[x][y]
				&& (arr[x][y] == 1 || arr[x][y] == 3 || arr[x][y] == 6 || arr[x][y] == 7))
			return true;
		return false;
	}

	private static boolean left(Point p) {	//왼쪽 확인
		int x = p.x;
		int y = p.y - 1;
		if (x >= 0 && y >= 0 && x < N && y < M && !visited[x][y]
				&& (arr[x][y] == 1 || arr[x][y] == 3 || arr[x][y] == 4 || arr[x][y] == 5))
			return true;
		return false;
	}

	private static boolean down(Point p) {	아래쪽 확인
		int x = p.x + 1;
		int y = p.y;
		if (x >= 0 && y >= 0 && x < N && y < M && !visited[x][y]
				&& (arr[x][y] == 1 || arr[x][y] == 2 || arr[x][y] == 4 || arr[x][y] == 7))
			return true;
		return false;
	}

	private static boolean up(Point p) {	//위쪽 확인
		int x = p.x - 1;
		int y = p.y;
		if (x >= 0 && y >= 0 && x < N && y < M && !visited[x][y]
				&& (arr[x][y] == 1 || arr[x][y] == 2 || arr[x][y] == 5 || arr[x][y] == 6))
			return true;
		return false;
	}
}