탈옥

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	10168	1962	1382	26.234%

문제

상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다.

이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다.

평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 나타나 있다.

감옥은 무인 감옥으로 죄수 두 명이 감옥에 있는 유일한 사람이다.

문은 중앙 제어실에서만 열 수 있다.

상근이는 특별한 기술을 이용해 제어실을 통하지 않고 문을 열려고 한다.

하지만, 문을 열려면 시간이 매우 많이 걸린다.

두 죄수를 탈옥시키기 위해서 열어야 하는 문의 개수를 구하는 프로그램을 작성하시오.

문을 한 번 열면 계속 열린 상태로 있는다.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다.

테스트 케이스의 수는 100개를 넘지 않는다.

첫째 줄에는 평면도의 높이 h와 너비 w가 주어진다. (2 ≤ h, w ≤ 100)

다음 h개 줄에는 감옥의 평면도 정보가 주어지며,

빈 공간은 ‘.’, 지나갈 수 없는 벽은 ‘*’, 문은 ‘#’, 죄수의 위치는 ‘$’이다.

상근이는 감옥 밖을 자유롭게 이동할 수 있고, 평면도에 표시된 죄수의 수는 항상 두 명이다.

각 죄수와 감옥의 바깥을 연결하는 경로가 항상 존재하는 경우만 입력으로 주어진다.

출력

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

예제 입력 1

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

예제 출력 1

4
0
9

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2013 J번

• 문제를 번역한 사람: baekjoon
• 데이터를 추가한 사람: doju, playsworld16, yukino

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 데이크스트라
• 0-1 너비 우선 탐색

---

통과된 코드

#include <iostream>
#include <vector>
#include <queue>

constexpr int MAX = 102;
using namespace std;

int _T, _H, _W;
int _DxDy[4][2] = { { 1, 0}, { 0, -1}, { 0, 1}, { -1, 0} };

vector<pair<int, int>> _Theifs;

char _Map[MAX][MAX];
int _IsVisted[3][MAX][MAX];

struct Pos
{
	int _X, _Y, _Doors;
	Pos(int _x, int _y, int _doors) : _X(_x), _Y(_y), _Doors(_doors) {};
	bool operator<(const Pos& other) const {
		return _Doors > other._Doors;
	}
};

void BFSFuction(int _x, int _y, int _n)
{
	for (int i = 0; i < MAX; i++)
		for (int j = 0; j < MAX; j++)
			_IsVisted[_n][i][j] = INT32_MAX;
	priority_queue<Pos> _BFSQueue;
	_BFSQueue.push(Pos(_x, _y, 0));
	_IsVisted[_n][_x][_y] = 0;
	while (!_BFSQueue.empty()) {
		int CntX = _BFSQueue.top()._X;
		int CntY = _BFSQueue.top()._Y;
		int Doors = _BFSQueue.top()._Doors;
		_BFSQueue.pop();
		if (_IsVisted[_n][CntX][CntY] < Doors)
			continue;
		for (int i = 0; i < 4; i++) {
			int dx = CntX + _DxDy[i][0];
			int dy = CntY + _DxDy[i][1];
			int doors = Doors;
			if (dx == -1 || dy == -1 || dx == _H + 2 || dy == _W + 2)
				continue;
			if (_Map[dx][dy] == '*')
				continue;
			else if (_Map[dx][dy] == '#')
				doors++;
			if (doors < _IsVisted[_n][dx][dy]) {
				_BFSQueue.push(Pos(dx, dy, doors));
				_IsVisted[_n][dx][dy] = doors;
			}
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> _T;
	while (_T--) {
		cin >> _H >> _W;
		_Theifs.clear();
		for (int i = 0; i < MAX; i++)
			for (int j = 0; j < MAX; j++)
				_Map[i][j] = ' ';
		for (int i = 1; i <= _H; i++) {
			string _Str;
			cin >> _Str;
			for (int j = 0; j < _W; j++) {
				_Map[i][j + 1] = _Str[j];
				if (_Str[j] == '$')
					_Theifs.push_back({ i, j + 1 });
			}
		}
		BFSFuction(_Theifs[0].first, _Theifs[0].second, 0);
		BFSFuction(_Theifs[1].first, _Theifs[1].second, 1);
		BFSFuction(0, 0, 2);
		int _Res = INT32_MAX;
		for (int i = 0; i <= _H + 1; i++)
			for (int j = 0; j <= _W + 1; j++) {
				if (_Map[i][j] == '*') continue;
				if (_IsVisted[0][i][j] == INT32_MAX || _IsVisted[1][i][j] == INT32_MAX || _IsVisted[2][i][j] == INT32_MAX)
					continue;
				int _sum = _IsVisted[0][i][j] + _IsVisted[1][i][j] + _IsVisted[2][i][j];
				if (_Map[i][j] == '#')
					_sum -= 2;
				_Res = min(_Res, _sum);
			}
		cout << _Res << "\n";
	}

	return 0;
}