[백준/BOJ] 백준 9328번 : 열쇠

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

9328번: 열쇠

빌딩의 밖을 빈 공간으로 감싸서 빌딩 밖을 표시하였고, 어떤 문을 발견했을 때 그때 그 문을 여는 열쇠가 없어도 나중에 그 열쇠를 발견할 수 도 있으므로 그 문의 정보를 저장해 놓았다. 

 

코드

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

int tc;
int h, w;
vector<string> board;
int have_key[26];
vector<pair<int, int>> discoverd_door[26];
int discovered[102][102];
int dxdy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };

int Solve(pair<int, int> start)
{
	discovered[start.first][start.second] = 1;

	int ret = 0;

	queue<pair<int, int>> q;
	q.push(start);

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

		//열쇠 위치에 왔을때
		if (board[here.first][here.second] >= 'a' && board[here.first][here.second] <= 'z')
		{
			//이 열쇠를 가진다
			have_key[board[here.first][here.second] - 'a'] = 1;

			//예전에 발견한 문 중에서 이 열쇠로 열 수 있는 문이 있을때 
			if (discoverd_door[board[here.first][here.second] - 'a'].size() != 0)
			{
				for (int i = 0; i < discoverd_door[board[here.first][here.second] - 'a'].size(); i++)
					q.push(discoverd_door[board[here.first][here.second] - 'a'][i]);
				discoverd_door[board[here.first][here.second] - 'a'].clear();
			}
		}

		//문서 위치에 왔을때
		else if (board[here.first][here.second] == '$')
		{
			ret++;
		}

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

			if (there.first >= 0 && there.first < h && there.second >= 0 && there.second < w && board[there.first][there.second] != '*' && discovered[there.first][there.second] == 0)
			{
				discovered[there.first][there.second] = 1;

				//there가 문이 있는 위치일때
				if (board[there.first][there.second] >= 'A' && board[there.first][there.second] <= 'Z')
				{
					//그 문을 열수 있는 열쇠가 있을때
					if (have_key[board[there.first][there.second] - 'A'] == 1)
					{
						q.push(there);
					}

					//그 문을 열 수 있는 열쇠가 없을때 (나중에 열쇠를 발견할 수도 있으므로 위치 정보를 저장해 놓는다)
					else
					{
						discoverd_door[board[there.first][there.second] - 'A'].push_back(there);
					}
				}

				else
					q.push(there);
			}
		}
	}

	return ret;
}

void Pre()
{
	board.clear();
	for (int i = 0; i < 26; i++)
	{
		have_key[i] = 0;
		discoverd_door[i].clear();
	}
	memset(discovered, 0, sizeof(discovered));
}

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

	string temp;
	string key;

	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;

		cin >> key;
		if (key != "0")
		{
			for (int i = 0; i < key.size(); i++)
				have_key[key[i] - 'a'] = 1;
		}

		//빌딩 밖인 (0,0)에서 탐색을 진행한다
		cout << Solve(make_pair(0, 0)) << "\n";
	}

	return 0;
}