평면도를 그래프로 생각할 수 있습니다. 정점은 평면도의 각 칸이 되고, 간선은 칸에서 인접한 상하좌우의 4개의 칸이 됩니다. 문제에서 구하고자 하는 것이 열어야 하는 문의 최솟값이기 때문에 간선의 가중치를 인접한 칸에 문이 없을 경우 , 있을 경우 로 정의해서 그래프에서의 최단 경로 알고리즘을 사용할 수 있습니다. 보통 가중치가 있는 그래프에서 최단 경로는 다익스트라 알고리즘을 사용하지만, 가중치가 과 뿐인 경우는 BFS를 사용할 수도 있습니다. BFS의 시간 복잡도는 로 인 다익스트라보다 더 효율적입니다.
만약 감옥에 죄수가 한 명만 있다고 가정해보겠습니다. 상근이의 위치에서 최단 경로 알고리즘을 사용하면 열어야 하는 문의 최솟값은 쉽게 구할 수 있습니다. 그렇다면 각각의 죄수까지의 최단경로를 더한 것이 전체 문제의 답일까요? 예제 입력의 세 번째 테스트 케이스만 봐도 아님을 알 수 있습니다.
평면도를 늘려서 상근이의 위치를 추가해주겠습니다. 평면도를 빈 공간으로 둘러 싼다면 둘러 싼 곳 어디에 상근이가 있다고 가정하여도 문제의 답에는 변함이 없습니다. 저는 에 있다고 가정하겠습니다. 이 때, 상근이가 위치한 정점을 라고 하고 두 죄수가 위치한 곳을 각각 라고 하겠습니다.
S..........
.*#**#**#*.
.*#**#**#*.
.*#**#**#*.
.*#**.**#*.
.*#*#.#*#*.
.*A##*##B*.
.*#*****#*.
.*.#.#.#.*.
.*********.
...........
예제 입력의 세 번째 테스트 케이스에서 알 수 있듯이, 상근이가 돌아서 가더라도 전체 문제의 최적해인 경우가 있습니다. 돌아서 들리는 지점이 어떤 지점인지는 모르겠지만 그 위치를 라고 하겠습니다. 그래프로 표현하면 다음과 같습니다.
는 임의의 정점이므로 모두 될 수 있습니다. 그렇게 되면 그래프는 아래와 같이 생기겠죠
최단 거리는 사이의 최단 거리를 모두 더한 값이 됩니다. 그런데 사실 사이의 최단 거리나 사이의 최단 거리나 둘 다 동일합니다. 죄수 는 문을 열 수 없지만, 만약 문을 열어서 에 도달한다면 사실 그 과정은 에 도달한 상근이가 거꾸로 따라가면 그대로 열 수 있죠.
그래서 우리는 이 문제를 임의의 경유점 에서 나머지 정점 까지의 최단 거리의 합 중에서 최솟값을 찾는 문제로도 생각할 수 있고 에서 임의의 경유점 까지의 최단 거리의 합 중에서 최솟값을 찾는 문제로도 생각할 수 있습니다.
전자는 개의 경유점 에 대해서 BFS를 해야되는데 이래서는 시간 내에 돌아갈 수 없습니다.
후자는 BFS를 3번 하고 얻은 배열에서 세 개의 합이 가장 작은 것을 구하면 되니 이 편이 더 간단해 보입니다. 단 경유점 가 문인 경우 한 번만 열면 되는 문을 세 번 열게 되므로 이 경우 2를 빼줍니다.
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);
}
}
BFS를 세 번 하고, 번 순회에서 최솟값을 찾습니다.
BFS의 시간 복잡도는 이므로 시간 복잡도는 에 지배됩니다.
대회 테스트 케이스가 사이트에 올라와 있습니다. 물론 백준에서는 테스트 케이스가 더 추가되었을 수 있습니다.