골드1 - 백준 9328 열쇠

백준 9328 열쇠

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

접근방법

이 문제는 막힌 문이 있다면 위치를 저장해놓았다가 문에 맞는 열쇠를 획득하면 다시 queue에 추가하여 BFS를 실행하는 식으로 진행하였다.

풀이

처음 map을 입력받을 때, 모든 뚫려있는 문을 쉽게 찾기 위해서 겉에 빈 공간을 둘러주었다. 그리고 prepared_key 배열을 이용하여 현재 가지고 있는 열쇠와 BFS를 실행하면서 얻는 키들에 대한 정보를 저장해주었다.
BFS를 실행시키면서 'a'~'z'를 만나면 prepared_key 배열을 true로 바꿔주고, 'A'~'Z'를 만난다면 locked_door['해당 알파벳'] 백터에 좌표를 추가시켜주었다.

BFS가 한번 끝나면, prepared_key 배열을 확인하여 가지고 있는 열쇠로 locked_door에 저장되어있는 좌표를 queue에 추가시켜주어 다시 BFS를 실행시켰다. 결과적으로 갈 수 있는 곳은 전부 다 방문할 수 있으며 '$'의 개수를 세어주어 결과를 출력했다.

처음에는 prepared_key를 queue로 선언하여 열쇠를 하나씩 빼주었는데 이렇게 할 경우 이중으로 잠겨있는 곳은 도달하지 못했고 반례가 발생하였다. 그래서 열쇠를 사용해도 계속 쓸 수 있게 bool 배열로 선언해주어 26개의 키를 매번 확인해주는 식으로 진행하였다.

코드

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

vector<vector<pair<int, int>>> locked_door;
bool visited[102][102];
vector<string> map;
vector<vector<int>> dir = { {0,1}, {0,-1,}, {1,0}, {-1,0} };
bool prepared_key[27];

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

	int T;
	cin >> T;

	while (T--)
	{
		map.clear();
		locked_door.clear();
		memset(visited, false, sizeof(visited));
		memset(prepared_key, false, sizeof(prepared_key));

		int answer = 0;
		int h, w;
		cin >> h >> w;

		string temp;
		for (int i = 0; i < w + 2; i++)
			temp += '.';

		map.push_back(temp);

		for (int i = 0; i < h; i++)
		{
			string p = ".";
			string s;
			cin >> s;
			p += s;
			p += '.';
			map.push_back(p);
		}

		map.push_back(temp);

		for (int i = 0; i < 27; i++)
		{
			vector<pair<int, int>> tVec;
			locked_door.push_back(tVec);
		}

		string k;
		cin >> k;

		for (int i = 0; i < k.size(); i++)
		{
			if (k[i] == '0')
				break;

			prepared_key[k[i] - 'a'] = true;
		}

		queue<pair<int, int>> q;
		visited[0][0] = true;
		q.push({ 0,0 });
		
		while (!q.empty())
		{
			while (!q.empty())
			{
				int x = q.front().first;
				int y = q.front().second;
				q.pop();

				for (int i = 0; i < 4; i++)
				{
					int nx = x + dir[i][0];
					int ny = y + dir[i][1];

					if (nx < 0 || nx >= h + 2 || ny < 0 || ny >= w + 2)
						continue;
					if (visited[nx][ny])
						continue;
					if (map[nx][ny] == '*')
						continue;

					if (map[nx][ny] == '$')
					{
						answer++;
						q.push({ nx, ny });
						visited[nx][ny] = true;
						continue;
					}

					if (map[nx][ny] >= 'a' && map[nx][ny] <= 'z')
					{
						prepared_key[map[nx][ny] - 'a'] = true;
						q.push({ nx, ny });
						visited[nx][ny] = true;
						continue;
					}

					if (map[nx][ny] >= 'A' && map[nx][ny] <= 'Z')
					{
						locked_door[map[nx][ny] - 'A'].push_back({ nx, ny });
						visited[nx][ny] = true;
						continue;
					}

					q.push({ nx, ny });
					visited[nx][ny] = true;
				}
			}

			// 큐에 추가
			for(int i=0; i<27; i++)
			{
				if (!prepared_key[i])
					continue;
				int key = i;
				
				for (int i = 0; i < locked_door[key].size(); i++)
					q.push(locked_door[key][i]);
				locked_door[key].clear();
			}
		}

		cout << answer << '\n';
	}
	return 0;
}