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

문제

상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다.

평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 나타나 있다. 감옥은 무인 감옥으로 죄수 두 명이 감옥에 있는 유일한 사람이다.

문은 중앙 제어실에서만 열 수 있다. 상근이는 특별한 기술을 이용해 제어실을 통하지 않고 문을 열려고 한다. 하지만, 문을 열려면 시간이 매우 많이 걸린다. 두 죄수를 탈옥시키기 위해서 열어야 하는 문의 개수를 구하는 프로그램을 작성하시오. 문을 한 번 열면 계속 열린 상태로 있는다.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 수는 100개를 넘지 않는다.

첫째 줄에는 평면도의 높이 h와 너비 w가 주어진다. (2 ≤ h, w ≤ 100) 다음 h개 줄에는 감옥의 평면도 정보가 주어지며, 빈 공간은 '.', 지나갈 수 없는 벽은 '*', 문은 '#', 죄수의 위치는 '$'이다.

상근이는 감옥 밖을 자유롭게 이동할 수 있고, 평면도에 표시된 죄수의 수는 항상 두 명이다. 각 죄수와 감옥의 바깥을 연결하는 경로가 항상 존재하는 경우만 입력으로 주어진다.

출력

각 테스트 케이스마다 두 죄수를 탈옥시키기 위해서 열어야 하는 문의 최솟값을 출력한다.

예제 입출력

• 예제 입력 1

3
5 9
****#****
*..#.#..*
****.****
*$#.#.#$*
*********
5 11
*#*********
*$*...*...*
*$*.*.*.*.*
*...*...*.*
*********.*
9 9
*#**#**#*
*#**#**#*
*#**#**#*
*#**.**#*
*#*#.#*#*
*$##*##$*
*#*****#*
*.#.#.#.*
*********

• 예제 출력 1

4
0
9

Solution

#include <iostream>
#include <vector>
#include <queue>
#define MAX 102
#define INF 987654

using namespace std;

int N, M;
char MATRIX[MAX][MAX];
int Dist[3][MAX][MAX];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1 ,0 ,0};
vector<pair<int, int>> prisoner;

void init(){
	prisoner.clear();
	for(int i = 0; i < MAX; i++){
		fill_n(MATRIX[i], MAX, '.');
	}
	for(int i = 0; i < 3; i++){
		for(int j = 0; j < MAX; j++){
			fill_n(Dist[i][j], MAX, INF);
		}
	}
}

void Dijkstra(int X, int Y, int Pos){
	priority_queue<pair<int, pair<int, int>>> PQ;
	PQ.push({0, {X, Y}});
	Dist[Pos][X][Y] = 0;
	while (!PQ.empty()){
		int x = PQ.top().second.first;
		int y = PQ.top().second.second;
		int cost = -PQ.top().first;
		PQ.pop();
		if(Dist[Pos][x][y] < cost) continue;
		for(int i = 0; i < 4; i++){
			int nx = x + dx[i];
			int ny = y + dy[i];
			int curCost = cost;
			if(nx >= 0 && nx <= N+1 && ny >= 0 && ny <= M+1 && MATRIX[nx][ny] != '*'){
				if(MATRIX[nx][ny] == '#') curCost++;
				if(Dist[Pos][nx][ny] > curCost){
					PQ.push({-curCost, {nx, ny}});
					Dist[Pos][nx][ny] = curCost;
				}
			}
		}
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int T; cin >> T;
	while(T--){
		init();
		cin >> N >> M;
		for(int i = 1; i <= N; i++){
			for(int j = 1; j <= M; j++) {
				cin >> MATRIX[i][j];
				if(MATRIX[i][j] == '$') prisoner.push_back({i, j});
			}
		}
		Dijkstra(0, 0, 0);
		Dijkstra(prisoner[0].first, prisoner[0].second, 1);
		Dijkstra(prisoner[1].first, prisoner[1].second, 2);		
		int minimum = 99999;
		int cost = 99999;
		for(int i = 0; i <= N+1; ++i){
			for(int j = 0; j <= N+1; ++j){
				if(MATRIX[i][j] != '*'){
					cost = Dist[0][i][j] + Dist[1][i][j] + Dist[2][i][j];
					if(MATRIX[i][j] == '#') cost -= 2;
					minimum = min(minimum, cost);
				}
			}
		}
		cout << minimum << '\n';
	}
}

많이 어렵다. 다익스트라 알고리즘을 안다고 해결 할 수 있는 문제가 아니다.

우선 관점을 확고하게 둘 필요가 있다.
1. 감옥 안에 있는 죄수 2명
2. 그 둘을 탈출시키기 위해 존재하는 1명
이 세 명을 기준으로 다익스트라 알고리즘을 돌리면 된다.

주 된 아이디어는 다음과 같다. 현재 데이터를 입력 받을 때는 1부터 N ~ 1부터 M 사이의 데이터를 입력받았다. 하지만 전체 감옥 끝에 또 다른 공간이 있으면 어떨까?

감옥 테두리 외에 또 다른 공간이 존재하고 0, 0 위치에서 상근이가 문을 열어주는 입장이라면 어떨까 하는 아이디어가 중요하다.

void init(){
	prisoner.clear();
	for(int i = 0; i < MAX; i++){
		fill_n(MATRIX[i], MAX, '.');
	}
	for(int i = 0; i < 3; i++){
		for(int j = 0; j < MAX; j++){
			fill_n(Dist[i][j], MAX, INF);
		}
	}
}

그러므로 애초에 초기 세팅에서 MATRIX 데이터 전체를 .으로 처리한다. 귀찮게 일을 두번하지 않게 하기 위해서.

int N, M;
char MATRIX[MAX][MAX];
int Dist[3][MAX][MAX];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1 ,0 ,0};
vector<pair<int, int>> prisoner;

void Dijkstra(int X, int Y, int Pos){
	priority_queue<pair<int, pair<int, int>>> PQ;
	PQ.push({0, {X, Y}});
	Dist[Pos][X][Y] = 0;
	while (!PQ.empty()){
		int x = PQ.top().second.first;
		int y = PQ.top().second.second;
		int cost = -PQ.top().first;
		PQ.pop();
		if(Dist[Pos][x][y] < cost) continue;
		for(int i = 0; i < 4; i++){
			int nx = x + dx[i];
			int ny = y + dy[i];
			int curCost = cost;
			if(nx >= 0 && nx <= N+1 && ny >= 0 && ny <= M+1 && MATRIX[nx][ny] != '*'){
				if(MATRIX[nx][ny] == '#') curCost++;
				if(Dist[Pos][nx][ny] > curCost){
					PQ.push({-curCost, {nx, ny}});
					Dist[Pos][nx][ny] = curCost;
				}
			}
		}
	}
}

2차원 배열 데이터 내에서 다익스트라를 쓰는것과 동일하다. 여기서 Cost는 문을 여는 비용. 가장 첫 번째 Cost는 문을 아직 열지 않았으니 0 부터 시작한다.
각 인물별로 Dist 데이터는 따로 처리한다. 현재 위치에서 비용을 처리할 때, 만약 문을 만나면 비용을 1 추가한다.

하지만 특정 위치에서 여러 방향에 문이 있는 상황도 존재한다. 이럴 때를 대비하여 for문 내에서 4 방향에 대한 처리를 할 때 cost 데이터는 독립 된 변수로 처리해야 한다. (필자는 이 부분에서 실수가 계속 일어났었다.)
0,0에서 상근이가 열어주는 경우, 나머지 각 죄수들이 알아서 여는 경우 총 3가지 경우에 대하여 Dist 배열을 각각 구한다. 그 후 이 세가지 배열 내에 데이터를 비교하면 된다.

int minimum = 99999;
int cost = 99999;
for(int i = 0; i <= N+1; ++i){
	for(int j = 0; j <= N+1; ++j){
		if(MATRIX[i][j] != '*'){
			cost = Dist[0][i][j] + Dist[1][i][j] + Dist[2][i][j];
			if(MATRIX[i][j] == '#') cost -= 2;
			minimum = min(minimum, cost);
		}
	}
}
cout << minimum << '\n';

모든 가능한 좌표들을 서치하며 벽이 아닌 경우에는 Dist 데이터에 값이 갱신되어있을테니 세 가지 경우에 대한 Dist 값을 갱신한다. 만약 벽을 만나면 -2를 해 준다. 어차피 세 경우 다 해당 위치에서 Cost를 +1 했을테니 한 가지 경우로 처리하기 위해서다.

역시 플레티넘 문제는 어렵다. 매우 매우 고민하고 도움도 많이 받았던 문제. 기억에 각인하기 위해 기록한다.