BOJ 9376 - 탈옥 [C++]

 

문제

https://www.acmicpc.net/problem/9376

두 명의 죄수가 $H \times W$ 크기의 감옥에 갇혀 있다.

감옥을 구성하는 격자 칸은 빈 칸('.'), 벽('*'), 문('#'), 죄수('$')로 이루어져 있다.

두 죄수가 모두 감옥의 바깥으로 탈출하기 위해 열어야 하는 문의 최소 개수를 구하는 문제이다.

풀이

문의 개수가 충분히 적다면 문의 열림/닫힘 상태를 관리하는 비트마스킹 + BFS로 해결할 수 있으나, 이 문제에서는 먹히지 않는다.

 

답이 나올 수 있는 경우를 두 가지로 나눠보았다.

1. 두 명의 죄수가 만나지 않고 각각 탈출하는 경우

각 죄수를 시작점으로 두고 다익스트라 혹은 0-1 BFS로 탈출하는 최단 경로를 구한다.

2. 두 명의 죄수가 만나서 같이 탈출하는 경우

첫 번째 죄수를 시작점으로 둔 최단 경로 배열을 $A$,

두 번째 죄수를 시작점으로 둔 최단 경로 배열을 $B$,

바깥 지점들을 시작점으로 둔 최단 경로 배열을 $C$라고 하자.

 

두 죄수가 만나는 지점을 $(i, j)$라고 하면, $A[i][j] + B[i][j] + C[i][j]$가 답의 후보가 된다. $(i,j)$가 문이라면, 중복 계산을 피하기 위해 $2$만큼 빼준다.

위 값들 중 최소를 출력한다.

 

어떤 지점에서는 불필요한 문의 중복이 생길 수 있지만, 결과가 최소가 되는 중간 지점 적어도 하나 이상에 대해서는 올바른 결과를 내기 때문에 위 방법이 성립한다.

코드

 

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9 + 7;
const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,1,0,-1 };

int N, M;
char arr[100][100]{};
vector<vector<int>> A, B, C;
deque<tuple<int, int, int>> q;
int ax = -1, ay = -1, bx = -1, by = -1;

void bfs01(vector<vector<int>> &D) {
	while (!q.empty()) {
		auto [x, y, d] = q.front(); q.pop_front();
		if (d > D[x][y]) continue;
		for (int i = 0; i < 4; i++) {
			int xx = x + dx[i], yy = y + dy[i];
			if (xx < 0 || xx >= N || yy < 0 || yy >= M || arr[xx][yy] == '*') continue;
			int cost = arr[xx][yy] == '#' ? 1 : 0;
			if (D[xx][yy] > d + cost) {
				D[xx][yy] = d + cost;
				if (cost) q.emplace_back(xx, yy, d + cost);
				else q.emplace_front(xx, yy, d + cost);
			}
		}
	}
}

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int T;
	for (cin >> T; T--;) {
		ax = -1, ay = -1, bx = -1, by = -1;
		cin >> N >> M;
		for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == '$') {
				if (ax == -1) ax = i, ay = j;
				else bx = i, by = j;
			}
		}
		A = vector<vector<int>>(N, vector<int>(M, INF));
		B = vector<vector<int>>(N, vector<int>(M, INF));
		C = vector<vector<int>>(N, vector<int>(M, INF));

		q.emplace_back(ax, ay, 0);
		A[ax][ay] = 0;
		bfs01(A);

		q.emplace_back(bx, by, 0);
		B[bx][by] = 0;
		bfs01(B);

		for (int i = 0; i < M; i++) {
			if (arr[0][i] != '*') {
				int cost = arr[0][i] == '#' ? 1 : 0;
				C[0][i] = cost;
				if (cost) q.emplace_back(0, i, cost);
				else q.emplace_front(0, i, cost);
			}
			if (arr[N - 1][i] != '*') {
				int cost = arr[N - 1][i] == '#' ? 1 : 0;
				C[N - 1][i] = cost;
				if (cost) q.emplace_back(N - 1, i, cost);
				else q.emplace_front(N - 1, i, cost);
			}
		}
		for (int i = 0; i < N; i++) {
			if (arr[i][0] != '*') {
				int cost = arr[i][0] == '#' ? 1 : 0;
				C[i][0] = cost;
				if (cost) q.emplace_back(i, 0, cost);
				else q.emplace_front(i, 0, cost);
			}
			if (arr[i][M - 1] != '*') {
				int cost = arr[i][M - 1] == '#' ? 1 : 0;
				C[i][M - 1] = cost;
				if (cost) q.emplace_back(i, M - 1, cost);
				else q.emplace_front(i, M - 1, cost);
			}
		}
		bfs01(C);

		int aMin = INF, bMin = INF;
		for (int i = 0; i < N; i++) {
			aMin = min({ aMin, A[i][0], A[i][M - 1] });
			bMin = min({ bMin, B[i][0], B[i][M - 1] });
		}
		for (int j = 0; j < M; j++) {
			aMin = min({ aMin, A[0][j], A[N - 1][j] });
			bMin = min({ bMin, B[0][j], B[N - 1][j] });
		}
		int ans = aMin + bMin;
		for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) if (arr[i][j] != '*') {
			int to = A[i][j] + B[i][j] - (arr[i][j] == '#' ? 1 : 0);
			int from = C[i][j];
			if (to >= INF || from >= INF) continue;
			ans = min(ans, to + from - (arr[i][j] == '#' ? 1 : 0));
		}
		cout << ans << '\n';
	}

}