boj, 백준) 9376. 탈옥 ( C / C++)

1. 문제 링크

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

9376번: 탈옥

2. 문제 개요

감옥에서 죄수 두 명을 탈옥시켜야 한다. 평면도에는 벽과 문이 나타나 있고, 탈옥시켜야 하는 죄수의 위치도 나타나 있다. 탈출하기 위해 최소한의 문을 열려고 하는데, 열어야 하는 문의 최솟값을 구하는 프로그램 작성.

 

3. 문제 힌트

문이 중요한 역할을 함.

죄수로부터, 어떠한 좌표에 도달했을 때, 몇 개의 문을 열어야만 도달할 수 있는지를 나타내기 위해 queue가 아닌 deque를 써야 함.

 

밖에서 시작하는 것 1개, 죄수 각각 1개씩 해서 이 세 개가 만나는 곳이 곧 탈출하는 것을 의미.

꼭 두 죄수가 밖으로 나가지 않아도 됨.

 

4. 문제 풀이

감옥 밖 1명, 죄수 2명의 정보를 담을 배열이 필요하다. 각자 주어진 맵에 대해서 해당 좌표에 몇 개의 문을 열어야 갈 수 있는지에 대한 정보이다. 이 값을 알아내기 위해서는 deque를 사용해야 하는데,

왜냐하면 문을 열지 않는 빈공간('*')는 가중치가 0이라고 봐도 된다. 흔히 queue를 사용하는 BFS는 가중치가 1인 경우의 최단경로를 구하는 것이다. 따라서, 문이 존재하는 곳은 가중치가 1(push_back), 문이 없는 곳은 가중치가 0(push_front)를 사용해야한다.

 

또, 밖에서도 출발하기 때문에 세 사람(밖 1명, 안 2명)이 맵 어딘가에서 만난다면, 그게 바로 탈출한 것이다.

그래서 앞서 BFS로 구한 값을 맵의 모든 좌표에서 비교해봐야 한다.

 

만약 모두 만난 곳의 좌표가 #이라면, 값이 중복된 것이기 때문에 -2를 해주자.

 

 

5. 소스 코드

#include <cstdio>
#include <deque>
#include <vector>
#include <string.h>
using namespace std;

struct COORD {
	int y, x;
	int time;
};
const int dx[] = { 1,-1,0,0 };
const int dy[] = { 0,0,1,-1 };


int main(void)
{
	int t;
	scanf("%d", &t);

	while (t--)
	{
		int ret = 0x7fffffff;

		char map[102][102] = { 0 };
		int val[3][102][102];
		memset(val, -1, sizeof(val));
		vector<pair<int, int>> v;	// y, x
		int r, c;
		scanf("%d %d", &r, &c);

		for (int i = 1; i <= r; i++)
			for (int j = 1; j <= c; j++)
			{
				scanf("%c", &map[i][j]);
				if (map[i][j] == '\n')
				{
					j--;
					continue;
				}
				if (map[i][j] == '$')
					v.push_back(make_pair(i, j));
			}
		v.push_back(make_pair(0, 0));

		for (int i = 0; i < 3; i++)
		{
			deque<COORD> q;
			bool visited[102][102] = { false, };

			COORD start;
			start.y = v[i].first, start.x = v[i].second, start.time = 0;
			visited[start.y][start.x] = true;
			q.push_back(start);

			while (!q.empty())
			{
				COORD cur = q.front(); q.pop_front();
				val[i][cur.y][cur.x] = cur.time;
				for (int dir = 0; dir < 4; dir++)
				{
					COORD next;
					next.y = cur.y + dy[dir];
					next.x = cur.x + dx[dir];

					if (next.y < 0 || next.x <0 || next.y >r + 1 || next.x >c + 1 || map[next.y][next.x] == '*')
						continue;

					if (visited[next.y][next.x] == false)
					{
						if (map[next.y][next.x] == '#')
						{
							next.time = cur.time + 1;
							visited[next.y][next.x] = true;
							q.push_back(next);
						}
						else
						{
							next.time = cur.time;
							visited[next.y][next.x] = true;
							q.push_front(next);
						}

					}
				}
			}
		}
		//val[0]에 더하기
		for (int i = 0; i <= r + 1; i++)
			for (int j = 0; j <= c + 1; j++)
			{
				if (map[i][j] == '*')continue;

				int k = val[0][i][j] + val[1][i][j] + val[2][i][j];
				if (k == -3)
					continue;

				if (map[i][j] == '#')
					k -= 2;

				if (k < ret)
					ret = k;

			}
		printf("%d\n", ret);
	}

	return 0;
}

 

6. 결과