[백준/BOJ] 백준 9376번 : 탈옥

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

9376번: 탈옥

밖을 자유롭게 이동하는 것을 나타내도록 밖을 빈 공간('.')으로 표시하였고, 문제를 푸는 방법은 상근이(0,0위치), 죄수1, 죄수2 들의 위치에서 각각 탐색을 진행하여 어떤 지점에서 셋이 만났을 때 문을 연 총횟수가 가장 작은 지를 풀었다. 이때  상근이나 죄수1이나 죄수2나 못 가는 위치라면 그곳에서는 만날 수 없다는 것도 고려하였다. deque를 사용하여 문이 아닌 위치를 발견했을 때는 push_front를 하여 먼저 탐색하도록 하였다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <string>
#include <deque>
using namespace std;

int tc;
int h, w;
vector<string> board;
int discovered[102][102][3]; //discovered에는 상근이([][][0]), 죄수1([][][1]), 죄수2([][][2])가 특정 위치에서 문을 연 횟수를 저장했다
int dxdy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };
vector<pair<int, int>> human;

int Solve(pair<int, int> human0, pair<int, int> human1, pair<int, int> human2)
{
	int ret = 987654321;

	discovered[human0.first][human0.second][0] = 0; //상근이
	discovered[human1.first][human1.second][1] = 0; //죄수1
	discovered[human2.first][human2.second][2] = 0; //죄수2

	deque<pair<pair<int, int>, int>> q; //deque를 사용하였다
	q.push_back(make_pair(human0, 0));
	q.push_back(make_pair(human1, 1));
	q.push_back(make_pair(human2, 2));

	while (!q.empty())
	{
		pair<pair<int, int>, int> here = q.front();
		q.pop_front();

		for (int i = 0; i < 4; i++)
		{
			pair<pair<int, int>, int> there = make_pair(make_pair(here.first.first + dxdy[i][0], here.first.second + dxdy[i][1]), here.second);
			if (there.first.first >= 0 && there.first.first < h && there.first.second >= 0 && there.first.second < w && board[there.first.first][there.first.second] != '*' && discovered[there.first.first][there.first.second][there.second] == -1)
			{
				if (board[there.first.first][there.first.second] == '#')
				{
					discovered[there.first.first][there.first.second][there.second] = discovered[here.first.first][here.first.second][here.second] + 1;
					q.push_back(there);
				}

				else
				{
					discovered[there.first.first][there.first.second][there.second] = discovered[here.first.first][here.first.second][here.second];
					q.push_front(there); //문이 아닌 위치를 발견했을때는 push_front를 하여 먼저 탐색하도록 한다
				}
			}
		}
	}


	for (int i = 0; i < h; i++)
		for (int j = 0; j < w; j++)
		{
			if (board[i][j] != '*')
			{
				//상근이나 죄수1이나 죄수2나 못가는 위치라면 그곳에서는 만날 수 없다
				if (discovered[i][j][0] == -1 || discovered[i][j][1] == -1 || discovered[i][j][2] == -1)
					continue;

				//문 위치일때 셋이서 만났으면 그 문은 한명만 열면 되므로 discovered[i][j][0] + discovered[i][j][1] + discovered[i][j][2] 에서 -2를 한것이다
				if (board[i][j] == '#')
				{
					ret = min(ret, discovered[i][j][0] + discovered[i][j][1] + discovered[i][j][2] - 2); 
				}

				//문 위치가 아닌곳에서 세명이서 만났을때
				else
				{
					ret = min(ret, discovered[i][j][0] + discovered[i][j][1] + discovered[i][j][2]); 
				}
			}
		}

	return ret;
}

void Pre()
{
	board.clear();
	for (int i = 0; i < 102; i++)
		for (int j = 0; j < 102; j++)
			for (int k = 0; k < 3; k++)
				discovered[i][j][k] = -1;
	human.clear();
	human.push_back(make_pair(0, 0));
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	string temp;

	cin >> tc;

	for (int t = 0; t < tc; t++)
	{
		Pre();

		cin >> h >> w;

		//밖을 자유롭게 이동하는것을 나타내도록 빈공간('.')으로 표시하였다
		temp = "";
		for (int i = 0; i < w; i++)
			temp += ".";
		board.push_back(temp);

		for (int i = 0; i < h; i++)
		{
			cin >> temp;
			temp = "." + temp + ".";
			board.push_back(temp);
		}

		temp = "";
		for (int i = 0; i < w; i++)
			temp += ".";
		board.push_back(temp);

		//밖을 빈공간('.')으로 채웠으므로 높이와 너비 증가
		h = h + 2;
		w = w + 2;

		for (int i = 0; i < h; i++)
			for (int j = 0; j < w; j++)
			{
				if (board[i][j] == '$')
					human.push_back(make_pair(i, j));
			}

		cout << Solve(human[0], human[1], human[2]) << "\n";
	}

	return 0;
}