[백준] 09376번 - 탈옥 / C++

문제

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

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

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

 

입력

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

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

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

 

출력

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

 

코드

#include <iostream>
#include <string>
#include <deque>
#include <cstring>
#include <climits>

using namespace std;

struct pos 
{
	int r;
	int c;

	void init(int r, int c)
	{
		this->r = r;
		this->c = c;
	}
};

int H;
int W;
string prison[102];		// 감옥의 상태
int door[102][102][3];		// 각 좌표에 도착하기 위해 열어야 하는 문의 개수
deque<pos> people;		// 세 사람의 초기 위치

// 모든 메모리를 리셋
void init()
{
	int i;

	for (i = 0; i <= H + 1; i++)
		prison[i].clear();
	memset(door, -1, sizeof(door));
	people.clear();
}

// 입력값을 저장
void input()
{
	int i, j;
	string s;
	pos p;

	cin >> H >> W;
	// 감옥 밖을 빈 공간으로 저장
	s.resize(W + 2, '.');
	prison[0] = s;
	prison[H + 1] = s;
	// 상근이의 위치를 추가
	p.init(0, 0);
	people.push_back(p);
	for (i = 1; i <= H; i++)
	{
		cin >> s;
		// 감옥 밖을 빈 공간으로 저장
		prison[i] = '.' + s + '.';
		for (j = 1; j <= W; j++)
		{
			// 죄수의 위치를 추가
			if (prison[i][j] == '$')
			{
				p.init(i, j);
				people.push_back(p);
			}	
		}
	}
}

// 범위 내인지 확인
bool in_range(pos p)
{
	if (p.r < 0 || p.r > H + 1 || p.c < 0 || p.c > W + 1)
		return false;
	return true;
}

// k번 사람이 방문 가능한 모든 좌표에 대해 열어야 하는 문의 개수 저장
void bfs(int k)
{
	deque<pos> dq;	
	pos curr, next;
	int d[] = {-1, 1, 0, 0};
	int i;

	// 출발 좌표를 삽입
	next = people[k];
	door[next.r][next.c][k] = 0;
	dq.push_back(next);
	while (!dq.empty())
	{
		curr = dq.front();
		dq.pop_front();
		for (i = 0; i < 4; i++)
		{
			next.init(curr.r + d[i], curr.c + d[3 - i]);
			// 범위 밖이면 패스
			if (!in_range(next))
				continue;
			// 벽이면 패스
			if (prison[next.r][next.c] == '*')
				continue;
			// 이미 방문했으면 패스
			if (door[next.r][next.c][k] != -1)
				continue;
			// 문이면 열은 문의 개수를 증가시키고 뒤에 삽입
			if (prison[next.r][next.c] == '#')
			{
				door[next.r][next.c][k] = door[curr.r][curr.c][k] + 1;
				dq.push_back(next);
			}
			// 빈 공간이면 문의 개수를 유지하고 앞에 삽입
			else
			{
				door[next.r][next.c][k] = door[curr.r][curr.c][k];
				dq.push_front(next);
			}
			
		}
	}
}

// 세 사람이 만나기 위해 열어야 하는 문의 개수의 최솟값을 구함
int find_min()
{
	int i, j, k;
	int sum, res = INT_MAX;

	for (i = 0; i <= H + 1; i++)
	{
		for (j = 0; j <= W + 1; j++)
		{
			// 벽이면 패스
			if (prison[i][j] == '*')
				continue;
			// 세 사람이 연 문의 개수를 구함
			sum = 0;
			for (k = 0; k < 3; k++)
				sum += door[i][j][k];
			// 만난 곳이 문이라면 같은 문을 세 번 연 것이므로 2번은 무효
			if (prison[i][j] == '#')
				sum -= 2;
			// 문을 연 횟수가 음수인 경우는 유효하지 않으므로 패스
			if (sum < 0)
				continue;
			// 최솟값 갱신
			res = min(res, sum);
		}
	}
	return res;
}

int main()
{
	int t, T;
	int k;

	cin >> T;
	for (t = 0; t < T; t++)
	{
		init();
		input();
		for (k = 0; k < 3; k++)
			bfs(k);
		cout << find_min() << endl;
	}
	return 0;
}

 

문을 연 횟수가 작은 경우부터 확인해야 각 좌표에 대해 문을 연 횟수가 최소가 되는 경우를 구할 수 있다. 그러므로 문을 여는 경우는 뒤에 추가하고 열지 않는 경우는 앞에 추가하여 dq가 오름차순을 유지하도록 한다.

 

링크

9376번: 탈옥

inbdni/Baekjoon