[Java] 1953. 탈주범 검거

모의 SW 역량테스트 1953. 탈주범 검거

 

문제 출처:  https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq

SW Expert Academy

파이프와 방향을 표현하기 위해 상하좌우를 비트로 표현. BFS를 이용하여 문제를 해결.

 

전체 소스코드 아래 추가적인 설명이 있습니다.

---

- 전체 소스코드

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

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

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

		public String toString() {
			return "(" + x + ", " + y + ") = time " + time;
		}
	}

	static int N, M, L;
	static int startX, startY;
	static int[][] map;
	static int[][] dir = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };

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

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

		for (int test_case = 1; test_case <= T; test_case++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			startX = Integer.parseInt(st.nextToken());
			startY = Integer.parseInt(st.nextToken());
			L = Integer.parseInt(st.nextToken());
			map = new int[N][M];
			
			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());
				}
			}
			
			int count = 0;
			boolean[][] visit = new boolean[N][M];

			Queue<Point> q = new LinkedList<>();
			q.add(new Point(startX, startY, 1));
			visit[startX][startY] = true;
			while (!q.isEmpty()) {
				Point p = q.poll();
				if (p.time <= L)
					count++;
				else
					break;
				
				int dirInfo = getDirInfo(map[p.x][p.y]);
				for (int i = 0; i < 4; i++) {
					if ((dirInfo >> i & 1) == 1) {
						int nextX = p.x + dir[i][0];
						int nextY = p.y + dir[i][1];
						if (nextX >= 0 && nextX < N && nextY >= 0 && nextY < M) { // in boundary
							if (visit[nextX][nextY] == false && map[nextX][nextY] != 0) {
								int nextDir = getDirInfo(map[nextX][nextY]);
								int j;
								if (i % 2 == 0)
									j = i + 1;
								else 
									j = i - 1;
								if ((nextDir >> j & 1) == 1) {
									q.add(new Point(nextX, nextY, p.time+1));
									visit[nextX][nextY] = true;									
								}
							}
						}
					}
				}
				
			}
			
			bw.append("#"+test_case+" "+count+"\n");
		}
		bw.flush();
		bw.close();
		br.close();

	}

	// 상하좌우 4개의 비트로 표현
	private static int getDirInfo(int val) {
		int dir = 0;
		switch (val) {
		case 1:
			dir = 15;
			break;
		case 2:
			dir = 12;
			break;
		case 3:
			dir = 3;
			break;
		case 4:
			dir = 9;
			break;
		case 5:
			dir = 5;
			break;
		case 6:
			dir = 6;
			break;
		case 7:
			dir = 10;
			break;
		}
		return dir;
	}

}

 

---

- 풀이

 

시간 L동안 시작점에서 출발하여 시간이 지날 수 록 존재할 수 있는 위치는 이어져있는 동굴로 퍼져나갈 수 있다. 해결 방식은 BFS로 잡고 위치와 그 위치에 도달할 수 있는 시간을 변수로 가진 클래스 Point를 선언하였다.

 

 

• Point Class

static class Point {
		int x, y;
		int time;

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

		public String toString() {
			return "(" + x + ", " + y + ") = time " + time;
		}
}

 

큐에 시작점을 담고 큐가 빌 때까지 탐색을 진행한다. 탐색은 큐에서 하나의 Point를 꺼내어 해당 위치에 도달할 시간을 체크한다. L보다 더 오래걸려 해당 위치로 왔다면 탐색을 종료하고 아니라면 시간 내 존재할 수 있으므로 카운트를 한다. 이어서 이동할 수 있는 길에 대해 찾아 큐에 담아준다.

 

이동할 수 있는 길을 찾는 방법은 다음과 같다.

 

지도에서 값을 들고와 동굴의 모양에 따라 이동할 수 있는 곳에 대한 정보 값을 받아온다. 상하좌우를 각각 1비트를 할당하여 네 자릿수의 비트로 표현하기로한다. 이를 비트 연산자로 분석하여 해당 위치의 비트가 켜져 있으면 이동할 수 있는 방향이므로 해당 위치에 대해 유망하다고 판단한다. 하지만 이동할 수 있는 방향이 동굴이 존재하지 않거나 존재해도 통로가 맞지 않을 수도 있다. 그렇기 때문에 이동할 방향에 대해서도 통로가 일치함을 비트 연산자를 이용하여 확인한 후 유망하다면 다음 위치를 큐에 넣는다.

 

// 상하좌우 4개의 비트로 표현
private static int getDirInfo(int val) {
    int dir = 0;
    switch (val) {
    case 1:
        dir = 15;
        break;
    case 2:
        dir = 12;
        break;
    case 3:
        dir = 3;
        break;
    case 4:
        dir = 9;
        break;
    case 5:
        dir = 5;
        break;
    case 6:
        dir = 6;
        break;
    case 7:
        dir = 10;
        break;
    }
    return dir;
}
    

위 작업을 반복하여 시간이 L보다 크다면 탐색을 멈추고 현재까지의 count를 출력하여 해결하였다.

 

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

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

		for (int test_case = 1; test_case <= T; test_case++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			startX = Integer.parseInt(st.nextToken());
			startY = Integer.parseInt(st.nextToken());
			L = Integer.parseInt(st.nextToken());
			map = new int[N][M];
			
			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());
				}
			}
			
			int count = 0;
			boolean[][] visit = new boolean[N][M];

			Queue<Point> q = new LinkedList<>();
			q.add(new Point(startX, startY, 1));
			visit[startX][startY] = true;
			while (!q.isEmpty()) {
				Point p = q.poll();
				if (p.time <= L)
					count++;
				else
					break;
				
				int dirInfo = getDirInfo(map[p.x][p.y]);
				for (int i = 0; i < 4; i++) {
					if ((dirInfo >> i & 1) == 1) {
						int nextX = p.x + dir[i][0];
						int nextY = p.y + dir[i][1];
						if (nextX >= 0 && nextX < N && nextY >= 0 && nextY < M) { // in boundary
							if (visit[nextX][nextY] == false && map[nextX][nextY] != 0) {
								int nextDir = getDirInfo(map[nextX][nextY]);
								int j;
								if (i % 2 == 0)
									j = i + 1;
								else 
									j = i - 1;
								if ((nextDir >> j & 1) == 1) {
									q.add(new Point(nextX, nextY, p.time+1));
									visit[nextX][nextY] = true;									
								}
							}
						}
					}
				}
				
			}
			
			bw.append("#"+test_case+" "+count+"\n");
		}
		bw.flush();
		bw.close();
		br.close();

	}