[백준 9328번] 열쇠 / C++

문제

상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 필요하다. 상근이는 일부 열쇠를 이미 가지고 있고, 일부 열쇠는 빌딩의 바닥에 놓여져 있다.

상근이가 훔칠 수 있는 문서의 최대 개수를 구하는 프로그램을 작성하시오.

입력

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

각 테스트 케이스의 첫째 줄에는 지도의 높이와 너비 h와 w (2 ≤ h, w ≤ 100)가 주어진다. 다음 h개 줄에는 빌딩을 나타내는 w개의 문자가 주어지며, 각 문자는 다음 중 하나이다.

• '.'는 빈 공간을 나타낸다.
• '*'는 벽을 나타내며, 상근이는 벽을 통과할 수 없다.
• '$'는 상근이가 훔쳐야하는 문서이다.
• 알파벳 대문자는 문을 나타낸다.
• 알파벳 소문자는 열쇠를 나타내며, 그 문자의 대문자인 모든 문을 열 수 있다.

마지막 줄에는 상근이가 이미 가지고 있는 열쇠가 공백없이 주어진다. 만약, 열쇠를 하나도 가지고 있지 않는 경우에는 "0"이 주어진다.

상근이는 처음에는 빌딩의 밖에 있으며, 빌딩 가장자리의 빈 공간이나 문을 통해 빌딩 안팎을 드나들 수 있다. 각각의 문에 대해서, 그 문을 열 수 있는 열쇠의 개수는 0개, 1개, 또는 그 이상이고, 각각의 열쇠에 대해서, 그 열쇠로 열 수 있는 문의 개수도 0개, 1개, 또는 그 이상이다. 열쇠는 여러 번 사용할 수 있다.

출력

각 테스트 케이스 마다, 상근이가 훔칠 수 있는 문서의 최대 개수를 출력한다.

풀이

bfs를 사용하여 문제를 풀이한다. 막상 풀어보면 그렇게 어렵지 않은 문제다.

문제 풀이 과정은 다음과 같다.

1. 맵의 가장자리를 탐색하면서 벽이 아닌 지점이 있으면 큐에 해당 지점의 위치를 저장한다.

2. 상근이가 가지고 있는 열쇠 목록을 저장한다.

3. bfs 호출

3-1. 탐색 지점이 문인데 문에 맞는 열쇠를 가지고 있지 않다면 일단 해당 위치를 임시 맵에 저장한다.

방문 표시는 하지 않고 다음 지점을 탐색한다.

(이후에 열쇠를 새로 얻어서 다시 방문할 수도 있기 때문이다.) 

3-2. 탐색 지점에 새 열쇠가 있다면 열쇠 목록에 저장한다.

새 열쇠로 이전에 열지 못한 문을 열 수 있다면 임시 맵에서 위치들을 찾아 큐에 저장한다.

3-3. 문서 찾으면 개수+1

3-4. 현재 지점에서 상, 하, 좌, 우를 탐색하여 벽이 아닌 지점은 큐에 저장한다.

4. bfs의 결과를 정답 벡터에 저장

5. 사용한 배열들과 임시맵을 초기화 한다.

6. 1~5를 테스트케이스 수만큼 반복한다.

#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include <queue>
#include <string>
#include <iostream>
#include <map>
using namespace std;
#define MAX 100
//지도의 높이와 너비(행, 열)
int h, w;
char MAP[MAX][MAX];
bool visited[MAX][MAX];
//상근이가 가진 열쇠 목록
bool key[26];
//열쇠가 없어서 못 여는 문의 문자와 위치를 임시 저장
map<char, vector<pair<int, int>>> temp_key;
int dir[4][2] = { {-1,0}, {0,-1}, {1,0}, {0,1} };

int bfs(queue<pair<int,int>> need_visit) {
	int cnt = 0;

	while (!need_visit.empty()) {
		int x = need_visit.front().first;
		int y = need_visit.front().second;
		int c = MAP[x][y];
		need_visit.pop();

		//문에 맞는 열쇠가 없을 경우 위치 임시 저장하고 다음 지점 탐색
		if ('A' <= c && c <= 'Z') {
			char ch = tolower(c);
			if (!key[ch - 'a']) {
				//소문자로 저장
				temp_key[ch].push_back({ x, y });
				continue;
			}
		}
		
		if (!visited[x][y]) {
			visited[x][y] = true;
			//방문 지점에 새로운 열쇠가 있으면 key벡터에 추가
			if ('a' <= c && c <= 'z') {
				if (!key[c - 'a']) {
					key[c - 'a'] = true;
					//새 열쇠로 열 수 있는 문이 있으면 해당 위치 큐에 저장
					if (temp_key[c].size() != 0) {
						for (int i = 0; i < temp_key[c].size(); i++)
							need_visit.push({ temp_key[c][i].first, temp_key[c][i].second });
						temp_key[c].clear();
					}
				}
			}
			//문서 찾으면 문서 개수에 1 더함
			if (c == '$') 
				cnt++;

			for (int i = 0; i < 4; i++) {
				int nx = x + dir[i][0];
				int ny = y + dir[i][1];
				if (nx < 0 || nx >= h || ny < 0 || ny >= w)
					continue;
				if (MAP[nx][ny] == '*' || visited[nx][ny])
					continue;
				need_visit.push({ nx, ny });
			}
		}
	}

	return cnt;
}

int main() {
	int tc;
	string key_ex;
	vector<int> answer;

	cin >> tc;

	for (int i = 0; i < tc; i++) {
		queue<pair<int, int>> need_visit;
		cin >> h >> w;

		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				cin >> MAP[i][j];
				//지도 가장자리가 벽이 아닐 경우
				if (i == 0 || i == h - 1 || j == 0 || j == w - 1) {
					//탐색할 지점에 해당 위치를 넣음
					if (MAP[i][j] != '*') {
						need_visit.push({ i, j });
					}
				}
			}
		}
		cin >> key_ex;

		if (key_ex != "0") {
			//열쇠 목록 저장
			for (int i = 0; i < key_ex.size(); i++)
				key[key_ex[i] - 'a'] = true;
		}
		
		answer.push_back(bfs(need_visit));
		//사용한 배열들과 큐 초기화
		memset(visited, false, sizeof(visited));
		memset(MAP, 0, sizeof(MAP));
		memset(key, false, sizeof(key));
		temp_key.clear();
	}

	for (auto elem : answer)
		cout << elem << '\n';
}