백준 탈옥(9376)

axiom·2021년 6월 20일

탈옥

1. 힌트

1) 예제 입력에서 세 번째 테스트 케이스에서 알 수 있듯이, 상근이로부터 각각의 죄수로 가는 최단 거리를 더한 것이 전체 문제의 최적해가 아닙니다. 때로는 돌아서 가더라도 최적해인 경우가 있습니다.

2) 그렇기 때문에 돌아서 들리는 임의의 경유점 $X$ 를 정의하고 상근이로부터 $X$ 까지의 최단 거리에 $X$ 로부터 각각의 죄수들까지의 최단 거리를 더한 값을 구합니다. $X$ 는 물론 두 죄수의 위치가 될 수도 있고, 평면도에는 안나와있지만 상근이의 위치가 될 수도 있습니다.

3) 실제로는 죄수가 문을 열 수는 없지만, 만약 문을 열어서 경유점 $X$ 에 도달한다면 상근이 또한 $X$ 에서 원래 죄수가 있던 지점으로 갈 수 있습니다. 이 과정은 순서는 다르지만 결과는 동일합니다. 이렇게 하면 상근이와 각각의 죄수들의 위치에서 BFS해서 나머지 모든 정점까지의 최단 거리를 담은 배열 3개를 구한 뒤에, 가능한 경유점 $X$ 중에서 가장 최단 거리들의 합이 작은 것을 찾습니다.

2. 접근

1) 단순한 방법에서 시작할 수 있을까?

평면도를 그래프로 생각할 수 있습니다. 정점은 평면도의 각 칸이 되고, 간선은 칸에서 인접한 상하좌우의 4개의 칸이 됩니다. 문제에서 구하고자 하는 것이 열어야 하는 문의 최솟값이기 때문에 간선의 가중치를 인접한 칸에 문이 없을 경우 $0$ , 있을 경우 $1$ 로 정의해서 그래프에서의 최단 경로 알고리즘을 사용할 수 있습니다. 보통 가중치가 있는 그래프에서 최단 경로는 다익스트라 알고리즘을 사용하지만, 가중치가 $0$ 과 $1$ 뿐인 경우는 $0-1$ BFS를 사용할 수도 있습니다. BFS의 시간 복잡도는 $O(V+E)$ 로 $O(ElgV)$ 인 다익스트라보다 더 효율적입니다.

만약 감옥에 죄수가 한 명만 있다고 가정해보겠습니다. 상근이의 위치에서 최단 경로 알고리즘을 사용하면 열어야 하는 문의 최솟값은 쉽게 구할 수 있습니다. 그렇다면 각각의 죄수까지의 최단경로를 더한 것이 전체 문제의 답일까요? 예제 입력의 세 번째 테스트 케이스만 봐도 아님을 알 수 있습니다.

2) 문제를 단순화할 수 없을까?

평면도를 늘려서 상근이의 위치를 추가해주겠습니다. 평면도를 빈 공간으로 둘러 싼다면 둘러 싼 곳 어디에 상근이가 있다고 가정하여도 문제의 답에는 변함이 없습니다. 저는 $(0,\ 0)$ 에 있다고 가정하겠습니다. 이 때, 상근이가 위치한 정점을 $S$ 라고 하고 두 죄수가 위치한 곳을 각각 $A,\ B$ 라고 하겠습니다.

S..........
.*#**#**#*.
.*#**#**#*.
.*#**#**#*.
.*#**.**#*.
.*#*#.#*#*.
.*A##*##B*.
.*#*****#*.
.*.#.#.#.*.
.*********.
...........

예제 입력의 세 번째 테스트 케이스에서 알 수 있듯이, 상근이가 돌아서 가더라도 전체 문제의 최적해인 경우가 있습니다. 돌아서 들리는 지점이 어떤 지점인지는 모르겠지만 그 위치를 $X$ 라고 하겠습니다. 그래프로 표현하면 다음과 같습니다.

$X$ 는 임의의 정점이므로 $S,\ A,\ B$ 모두 될 수 있습니다. 그렇게 되면 그래프는 아래와 같이 생기겠죠

최단 거리는 $(S,\ X),\ (X,\ A),\ (X,\ B)$ 사이의 최단 거리를 모두 더한 값이 됩니다. 그런데 사실 $(X,\ A)$ 사이의 최단 거리나 $(A,\ X)$ 사이의 최단 거리나 둘 다 동일합니다. 죄수 $A,\ B$ 는 문을 열 수 없지만, 만약 문을 열어서 $X$ 에 도달한다면 사실 그 과정은 $X$ 에 도달한 상근이가 거꾸로 따라가면 그대로 열 수 있죠.

그래서 우리는 이 문제를 임의의 경유점 $X$ 에서 나머지 정점 $S,\ A,\ B$ 까지의 최단 거리의 합 중에서 최솟값을 찾는 문제로도 생각할 수 있고 $S,\ A,\ B$ 에서 임의의 경유점 $X$ 까지의 최단 거리의 합 중에서 최솟값을 찾는 문제로도 생각할 수 있습니다.
전자는 $h\times w$ 개의 경유점 $X$ 에 대해서 BFS를 해야되는데 이래서는 시간 내에 돌아갈 수 없습니다.
후자는 BFS를 3번 하고 얻은 $dist$ 배열에서 세 개의 합이 가장 작은 것을 구하면 되니 이 편이 더 간단해 보입니다. 단 경유점 $X$ 가 문인 경우 한 번만 열면 되는 문을 세 번 열게 되므로 이 경우 2를 빼줍니다.

3. 구현

import java.io.*;
import java.util.*;

public class Main {
	static int N, M;
	static char[][] S;
	
	static final int[] dy = { -1, 1, 0, 0 };
	static final int[] dx = { 0, 0, -1, 1 };
	
	static final int INF = 10000;
	
	static boolean inRange(int y, int x) { 
		return 0 <= y && y < N && 0 <= x && x < M; 
	}
	
	// 정점 s에서 나머지 모든 정점에 대한 최단 거리를 담은 배열 반환
	// 도달할 수 없는 정점이면 INF가 저장되어있다.
	static int[][] bfs(int[] s) {
		Deque<int[]> q = new LinkedList<>();
		q.offer(s);
		int[][] dist = new int[N][M];
		for (int i = 0; i < N; i++) Arrays.fill(dist[i], INF);
		dist[s[0]][s[1]] = 0;
		while (!q.isEmpty()) {
			int[] p = q.poll();
			int y = p[0]; int x = p[1];
			for (int d = 0; d < 4; d++) {
				int ny = y + dy[d]; int nx = x + dx[d];
				if (!inRange(ny, nx) || S[ny][nx] == '*' || dist[ny][nx] != INF)
					continue;
				if (S[ny][nx] == '#') q.offer(new int[] { ny, nx });
				// 빈 정점이라면 먼저 방문할 수 있도록 덱의 앞에 삽입한다
				else q.offerFirst(new int[] { ny, nx });
				dist[ny][nx] = dist[y][x] + (S[ny][nx] == '#' ? 1 : 0);
			}
		}
		return dist;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder bw = new StringBuilder();
		int TC = Integer.parseInt(br.readLine());
		while (TC-- > 0) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			// 주변을 빈 공간으로 채워주기 위해 크기를 늘린다
			N = Integer.parseInt(st.nextToken()) + 2;
			M = Integer.parseInt(st.nextToken()) + 2;
			S = new char[N][M];
			Arrays.fill(S[0], '.');
			for (int i = 1; i <= N - 2; i++) S[i][0] = S[i][M - 1] = '.';
			Arrays.fill(S[N - 1], '.');
			int[] A = null; int[] B = null;
			for (int i = 1; i <= N - 2; i++) {
				String row = br.readLine();
				for (int j = 1; j <= M - 2; j++) {
					S[i][j] = row.charAt(j - 1);
					if (S[i][j] == '$') {
						if (A == null) A = new int[] { i, j };
						else B = new int[] { i, j };
					}
				}
			}
			// A, B, S각각에 대해 최단 거리를 담고 있는 배열
			int[][][] dist = new int[3][N][M];
			dist[0] = bfs(A);
			dist[1] = bfs(B);
			dist[2] = bfs(new int[] { 0, 0 });
			int min = 30000;
			for (int i = 0; i < N; i++)
				for (int j = 0; j < M; j++)
					min = Math.min(min, 
				dist[0][i][j] + dist[1][i][j] + dist[2][i][j] - 
				(S[i][j] == '#' ? 2 : 0));
			bw.append(min).append("\n");
		}
		System.out.print(bw);
	}
	
}