문제
https://www.acmicpc.net/problem/9376
이해
NxM 격자판에 벽, 문, 탈옥수 2명이 있습니다.
상근이는 격자판의 문을 열어 탈옥수 2명을 모두 탈출시키려고 합니다.
모두 탈출하기 위해 열어야하는 문의 최솟값을 구하면 되겠습니다.
접근
격자판, 최솟값에 대한 문제는 BFS를 떠올리시는 것이 좋습니다. 상근이는 최소의 문을 열어 탈옥수 2명을 탈출시켜야 합니다.
가장 직관적인 방법으로는 상근이를 DFS 완전탐색을 수행해 가장 빠른 경우를 찾는 것입니다. 하지만 단순 격자판이 아니라 문이 존재하며 탈옥수 두명을 모두 만나야하기 때문에 경우의 수가 비약적으로 많아집니다.
문제에서 한 가지 힌트를 얻을 수 있습니다. 상근이는 감옥 밖 어디서든지 감옥에 접근할 수 있습니다. 따라서, 바깥으로 연결된 격자라면 어디든지 출구가 될 수 있습니다. 이 말은 즉, 격자를 한칸씩 연장했을 때 생기는 외부 격자 어디든지 출발점이 될 수 있는 것입니다.
또한, 문제에서 요구하는 것은 출구까지의 거리가 아닌 문의 최솟값 입니다. 거리에 대해서는 별로 궁금하지 않습니다. 중요한 것은 문을 연 갯수이기 때문에 일반적인 BFS의 최단거리 방식보다 특별한 로직이 필요합니다.
BFS의 유형 중에 0-1 BFS가 있습니다. 0-1 BFS는 간선의 가중치가 0 또는 1일때 사용됩니다. 알고리즘에 대해서 간단히 요약하자면 특정 노드를 방문했을 때 연결된 간선의 가중치를 판단하여 0 이라면 먼저 방문하도록 하고 1이라면 뒤에서 방문하도록 합니다.
0-1 BFS를 본 문제에 적용할 수 있습니다. 문이 없는 격자는 가중치가 0, 문이 있는 격자는 가중치가 1이기 때문입니다.
여기까지 정리하자면 0-1 BFS를 돌려 한 점에서부터 모든 격자까지의 최소 가중치 (문을 연 갯수)를 구할 수 있습니다. 출발점이 되는 한 점은 상근이의 경우에는 외부의 임의의 격자가 되겠습니다.
그렇다면 문의 최솟값은 어떻게 구할 수 있을까요? 조금 이해하기 어려울수도 있지만 상근이와 마찬가지로 탈옥수 두 명도 문을 열 수 있다고 가정합시다. (결국 탈옥수 본인이 직접 탈출하든지 상근이가 문을 열어주든지 같은 문을 열어야 하기 때문입니다.)
상근, 탈옥수1, 탈옥수2 모두가 문을 열고 나갈 때 한 점에 만난다면? 외부에서 온 상근이는 외부로부터 문을 열면서 왔기 때문에 탈옥수와 상근이가 만난다면 그 즉시 탈옥수는 탈옥한 것과 같습니다.
그렇다면 최솟값은 어떻게 될까요? 바로 이 3명의 모든 격자까지 문을 연 횟수를 모두 합하고 그 중에서 가장 작은 값이 위치한 격자가 되겠습니다. 어느 경우가 됐든 3명이 해당 위치에서 만난다는 것과 같기 때문입니다.
위 자료를 참고하시면 이해하는데 도움이 되실 겁니다.
풀이
private static int solution() {
int ret = INF;
int[][] helperMinBoard = bfs(helper);
int[][] prisoner1MinBoard = bfs(prisoner1);
int[][] prisoner2MinBoard = bfs(prisoner2);
int[][] sumBoard = new int[h + 2][w + 2];
// PrintForDebug(helperMinBoard, prisoner1MinBoard, prisoner2MinBoard);
for (int i = 0; i < h + 2; i++) {
for (int j = 0; j < w + 2; j++) {
sumBoard[i][j] = helperMinBoard[i][j] + prisoner1MinBoard[i][j] + prisoner2MinBoard[i][j];
if (board[i][j] == DOOR) {
sumBoard[i][j] -= 2;
}
ret = Math.min(ret, sumBoard[i][j]);
}
}
return ret;
}3명의 0-1 BFS를 수행한 격자를 가지고 합을 구한 뒤 최솟값의 위치를 찾습니다. 해당 위치가 만일 문이 위치한 경우라면 3명 중 1명만이 열면 되기 때문에 2를 빼줍니다.
while (!dq.isEmpty()) {
Point cur = dq.poll();
for (int i = 0; i < 4; i++) {
int nx = cur.x + d[0][i];
int ny = cur.y + d[1][i];
if (IsOutBound(nx, ny) || board[nx][ny] == WALL || visited[nx][ny]) {
continue;
}
if (board[nx][ny] == GROUND) {
visited[nx][ny] = true;
retBoard[nx][ny] = retBoard[cur.x][cur.y];
dq.addFirst(new Point(nx, ny));
} else {
visited[nx][ny] = true;
retBoard[nx][ny] = retBoard[cur.x][cur.y] + 1;
dq.addLast(new Point(nx, ny));
}
}
}0-1 BFS의 동작과정입니다. 특이하게도 Deque을 사용합니다. 다음 방문할 곳이 땅이라면 가중치가 0이기 때문에 Deque의 앞에 삽입하고 문이라면 가중치가 1이기 때문에 Deque의 뒤에 삽입합니다.
- 추가 0-1 BFS는 사실 다익스트라의 개념과 비슷합니다. 가중치가 짧은 것을 먼저 방문하여 갱신한다는 점이 비슷합니다. (위 코드에서 Deque 대신 PriorityQueue를 사용해도 됩니다.) 단, 가중치가 0 혹은 1인 경우에만 다익스트라처럼 사용할 수 있습니다.
코드
package baekjoon;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.StringTokenizer;
import java.awt.Point;
public class prob9376 {
static final int INF = 1_000_000;
static final int GROUND = 0;
static final int WALL = 1;
static final int DOOR = 2;
static final int[][] d = { { -1, 0, 1, 0 }, { 0, 1, 0, -1 } };
static int T;
static StringBuilder sb = new StringBuilder();
static StringTokenizer st = null;
static int h, w;
static int[][] board;
static Point helper;
static Point prisoner1;
static Point prisoner2;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
T = Integer.parseInt(br.readLine());
for (int test_case = 1; test_case <= T; test_case++) {
st = new StringTokenizer(br.readLine());
h = Integer.parseInt(st.nextToken());
w = Integer.parseInt(st.nextToken());
board = new int[h + 2][w + 2];
for (int i = 0; i < h + 2; i++) {
Arrays.fill(board[i], GROUND);
}
prisoner1 = null;
prisoner2 = null;
for (int i = 1; i <= h; i++) {
String s = br.readLine();
for (int j = 1; j <= w; j++) {
switch (s.charAt(j - 1)) {
case '#':
board[i][j] = DOOR;
break;
case '*':
board[i][j] = WALL;
break;
case '$':
if (prisoner1 == null) {
prisoner1 = new Point(i, j);
} else {
prisoner2 = new Point(i, j);
}
case '.':
board[i][j] = GROUND;
break;
}
}
}
helper = new Point(0, 0);
sb.append(solution()).append("\n");
}
System.out.println(sb.toString());
}
private static int solution() {
int ret = INF;
int[][] helperMinBoard = bfs(helper);
int[][] prisoner1MinBoard = bfs(prisoner1);
int[][] prisoner2MinBoard = bfs(prisoner2);
int[][] sumBoard = new int[h + 2][w + 2];
// PrintForDebug(helperMinBoard, prisoner1MinBoard, prisoner2MinBoard);
for (int i = 0; i < h + 2; i++) {
for (int j = 0; j < w + 2; j++) {
sumBoard[i][j] = helperMinBoard[i][j] + prisoner1MinBoard[i][j] + prisoner2MinBoard[i][j];
if (board[i][j] == DOOR) {
sumBoard[i][j] -= 2;
}
ret = Math.min(ret, sumBoard[i][j]);
}
}
return ret;
}
private static void PrintForDebug(int[][] helperMinBoard, int[][] prisoner1MinBoard, int[][] prisoner2MinBoard) {
System.out.println("=============helper=============");
for (int i = 0; i < h + 2; i++) {
for (int j = 0; j < w + 2; j++) {
System.out.print(helperMinBoard[i][j] >= INF ? 9 : helperMinBoard[i][j]);
System.out.print(" ");
}
System.out.println("\n");
}
System.out.println("=============p1=============");
for (int i = 0; i < h + 2; i++) {
for (int j = 0; j < w + 2; j++) {
System.out.print(prisoner1MinBoard[i][j] >= INF ? 9 : prisoner1MinBoard[i][j]);
System.out.print(" ");
}
System.out.println("\n");
}
System.out.println("=============p2=============");
for (int i = 0; i < h + 2; i++) {
for (int j = 0; j < w + 2; j++) {
System.out.print(prisoner2MinBoard[i][j] >= INF ? 9 : prisoner2MinBoard[i][j]);
System.out.print(" ");
}
System.out.println("\n");
}
}
private static int[][] bfs(Point p) {
int[][] retBoard = new int[h + 2][w + 2];
for (int i = 0; i < h + 2; i++) {
Arrays.fill(retBoard[i], INF);
}
Deque<Point> dq = new ArrayDeque<>();
boolean[][] visited = new boolean[h + 2][w + 2];
dq.add(p);
visited[p.x][p.y] = true;
retBoard[p.x][p.y] = 0;
while (!dq.isEmpty()) {
Point cur = dq.poll();
for (int i = 0; i < 4; i++) {
int nx = cur.x + d[0][i];
int ny = cur.y + d[1][i];
if (IsOutBound(nx, ny) || board[nx][ny] == WALL || visited[nx][ny]) {
continue;
}
if (board[nx][ny] == GROUND) {
visited[nx][ny] = true;
retBoard[nx][ny] = retBoard[cur.x][cur.y];
dq.addFirst(new Point(nx, ny));
} else {
visited[nx][ny] = true;
retBoard[nx][ny] = retBoard[cur.x][cur.y] + 1;
dq.addLast(new Point(nx, ny));
}
}
}
return retBoard;
}
private static boolean IsOutBound(int nx, int ny) {
return nx < 0 || nx >= h + 2 || ny < 0 || ny >= w + 2;
}
}