[BOJ] 9328 - 열쇠

1. 문제 해석

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

9328번: 열쇠

• 최대 100*100 크기의 이차원 배열의 주어진 맵에서 획득 가능한 문서($)의 개수를 구하는 문제입니다.
• 알파벳 대문자(A~Z)는 문을 의미하고 알파벳 소문자(a~z)는 문을 열 수 있는 열쇠입니다.
• 열쇠는 처음에 몇개가 주어질 수도 있고 아닐수도 있습니다. 맵을 이동하며 열쇠를 획득할 수 있습니다.
• 열쇠 획득 후에 지나온 길을 다시 지나서 열지 못했던 문을 열 수 있습니다.
• 하나의 열쇠로 여러개의 문을 열 수 있습니다.
• 맵 밖으로 날갈 수 있습니다.

 

2. 접근 방법

• 시작 위치가 특정되지 않고 맵 밖으로 나갈 수 있기 때문에 맵 테두리에 이동할 수 있는 길을 만들었다. 큐에 (0, 0)을 시작점으로 넣고 탐색을 시작한다. 방문 표시를 통해 갈 수 있는 길일지 표시한다.
• 1) 이동 중 문을 만났을 때 가지고 있는 열쇠로 문을 열 수 있으면 열고 없으면 벡터에 해당 문의 좌표를 넣어 준다.
• 2) 이동 중 새로운 열쇠를 만나면 카운팅 해준다.
• 3) 이동 종료 후 새로 획득한 열쇠가 있다면 벡터에 있는 문의 좌표를 이용하여 문을 확인 한다.
  열 수 있는 문이 있다면 큐에 넣고 1)번 부터 다시 반복한다.
• 새로 획득한 열쇠가 없다면 탐색을 종료한다.
• (0, 0)에서 다시 한 번 탐색을 진행한다. 이전에 방문 표시 했던 길로 이동한다. 문서를 찾으면 카운팅해준다.

 

 

3. 소스코드

#include <iostream>
#include <queue>
#include <string>
#include <vector>
using namespace std;
int T, N, M;
char map[111][111];
bool check[111][111];
bool key[111];
bool vis[111][111];
int dr[4] = { -1,0,1,0 };
int dc[4] = { 0,1,0,-1 };
void init() {
	for (int i = 0; i < 111; i++) {
		key[i] = false;
		for (int j = 0; j < 111; j++) {
			map[i][j] = '.';
			check[i][j] = false;
			vis[i][j] = false;
		}
	}
}
bool isRange(int r, int c) {
	if (r < 0 || r > N + 1 || c < 0 || c > M + 1) return false;
	return true;
}
void findKey() {
	vector<pair<int, int>> v;
	queue<pair<int, int>> q;
	int countNewKey;
	check[0][0] = true;
	q.push({ 0, 0 });
	while (true) {
		countNewKey = 0;
		while (!q.empty()) {
			int nowR = q.front().first;
			int nowC = q.front().second;
			q.pop();
			for (int k = 0; k < 4; k++) {
				int nextR = nowR + dr[k];
				int nextC = nowC + dc[k];
				if (!isRange(nextR, nextC)) continue;
				if (check[nextR][nextC]) continue;
				if (map[nextR][nextC] == '*') continue;
				if (map[nextR][nextC] == '.') {
					check[nextR][nextC] = true;
					q.push({ nextR, nextC });
				}
				else if (map[nextR][nextC] == '$') {
					check[nextR][nextC] = true;
					q.push({ nextR, nextC });
				}
				else if ('a' <= map[nextR][nextC] && map[nextR][nextC] <= 'z') {
					int idx = map[nextR][nextC] - 'a';
					if (!key[idx]) {
						key[idx] = true;
						countNewKey += 1;
					}
					check[nextR][nextC] = true;
					q.push({ nextR, nextC });
				}
				else if ('A' <= map[nextR][nextC] && map[nextR][nextC] <= 'Z') {
					int idx = map[nextR][nextC] - 'A';
					if (key[idx]) {
						check[nextR][nextC] = true;
						q.push({ nextR, nextC });
					}
					else {
						v.push_back({ nextR,nextC });
					}
				}
			}
		}
		if (countNewKey == 0) break;
		for (int i = 0; i < v.size(); i++) {
			int idx = map[v[i].first][v[i].second] - 'A';
			if (key[idx]) {
				check[v[i].first][v[i].second] = true;
				q.push(v[i]);
			}
		}
	}
	
}
int countDocument() {
	int count = 0;
	queue<pair<int, int>> q;
	vis[0][0] = true;
	q.push({ 0, 0 });
	while (!q.empty()) {
		int nowR = q.front().first;
		int nowC = q.front().second;
		q.pop();
		for (int k = 0; k < 4; k++) {
			int nextR = nowR + dr[k];
			int nextC = nowC + dc[k];
			if (!isRange(nextR, nextC)) continue;
			if (vis[nextR][nextC]) continue;
			if (map[nextR][nextC] == '*') continue;
			if (!check[nextR][nextC]) continue;
			if (map[nextR][nextC] == '$') {
				count += 1;
			}
			vis[nextR][nextC] = true;
			q.push({ nextR, nextC });
		}
	}
	return count;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> T;
	for (int test_case = 0; test_case < T; test_case++) {
		init();
		// vector<pair<int, int>> vec[50];
		cin >> N >> M;
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= M; j++) {
				cin >> map[i][j];
			}
		}
		string str;
		cin >> str;
		if (str[0] != '0') {
			for (int i = 0; i < str.size(); i++) {
				key[str[i] - 'a'] = true;
			}
		}
		findKey();
		int ans = countDocument();
		cout << ans << '\n';
	}
	return 0;
}