[백준/BOJ] 백준 1194번 : 달이 차오른다, 가자.

www.acmicpc.net/problem/1194

1194번: 달이 차오른다, 가자.

탐색을 하며 가지고 있는 열쇠 정보를 비트 연산을 통해 저장했으며, discovered와 depth에 위치상황뿐만 아니라 그때의 가지고 있는 열쇠 상황도 고려하여 문제를 해결했다.

 

코드

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

int n, m;
vector<string> board;
int dxdy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };
int discovered[50][50][1 << 6];
int depth[50][50][1 << 6];

void Pre()
{
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			for (int k = 0; k < (1 << 6); k++)
				discovered[i][j][k] = 0;
}

int Solve(pair<int, int> start)
{
	Pre();

	queue<pair<pair<int, int>, int>> q;

	discovered[start.first][start.second][0] = 1;
	depth[start.first][start.second][0] = 0;
	q.push(make_pair(start, 0));

	while (!q.empty())
	{
		pair<int, int> here = q.front().first;
		int here_have_key = q.front().second;
		q.pop();

		//출구일때
		if (board[here.first][here.second] == '1')
			return depth[here.first][here.second][here_have_key];

		for (int i = 0; i < 4; i++)
		{
			pair<int, int> there = make_pair(here.first + dxdy[i][0], here.second + dxdy[i][1]);
			int there_have_key = here_have_key;

			if (there.first >= 0 && there.first < n && there.second >= 0 && there.second < m && board[there.first][there.second] != '#')
			{
				//빈곳 또는 출구 또는 입구일때
				if (board[there.first][there.second] == '.' || board[there.first][there.second] == '1' || board[there.first][there.second] == '0')
				{
					there_have_key = here_have_key;

					if (discovered[there.first][there.second][there_have_key] == 0)
					{
						discovered[there.first][there.second][there_have_key] = 1;
						depth[there.first][there.second][there_have_key] = depth[here.first][here.second][here_have_key] + 1;
						q.push(make_pair(there, there_have_key));
					}
				}

				//열쇄일때
				else if (board[there.first][there.second] >= 'a' && board[there.first][there.second] <= 'z')
				{
					there_have_key = here_have_key;
					there_have_key |= (1 << (board[there.first][there.second] - 'a'));

					if (discovered[there.first][there.second][there_have_key] == 0)
					{
						discovered[there.first][there.second][there_have_key] = 1;
						depth[there.first][there.second][there_have_key] = depth[here.first][here.second][here_have_key] + 1;
						q.push(make_pair(there, there_have_key));
					}
				}

				//문일때
				else if (board[there.first][there.second] >= 'A' && board[there.first][there.second] <= 'Z')
				{
					there_have_key = here_have_key;

					//there문에 대한 열쇠가 있을때
					if ((here_have_key & (1 << (board[there.first][there.second] - 'A'))) == (1 << (board[there.first][there.second] - 'A')))
					{
						if (discovered[there.first][there.second][there_have_key] == 0)
						{
							discovered[there.first][there.second][there_have_key] = 1;
							depth[there.first][there.second][there_have_key] = depth[here.first][here.second][here_have_key] + 1;
							q.push(make_pair(there, there_have_key));
						}
					}
				}
			}
		}

	}

	return -1;
}

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

	cin >> n >> m;

	string input;
	pair<int, int> start;

	for (int i = 0; i < n; i++)
	{
		cin >> input;

		for (int j = 0; j < input.size(); j++)
		{
			if (input[j] == '0')
				start = make_pair(i, j);
		}

		board.push_back(input);
	}

	cout << Solve(start);

	return 0;
}