백준 9328 - 열쇠

문제링크

• 백준 9328

문제설명

• h x w 크기의 문자로 이루어진 지도가 주어진다.
  • .: 빈칸
  • *: 벽을 나타내며 통과할 수 없다.
  • $: 훔쳐야하는 문서
  • 알파벳 대문자는 문을 나타낸다.
  • 알파벳 소문자는 열쇠를 나타내며, 그 문자의 대문자인 모든 문을 열 수 있다.
• 상근이가 이미 가지고 있는 열쇠가 공백없이 문자열 형태로 주어진다.
  • 열쇠를 가지고 있지 않은 경우 “0” 이 주어진다.
• 상근이가 최대로 훔칠 수 있는 문서의 개수를 구하라.

문제접근

• 문제 해결에 어려웠던 점은 서로 다른 경로에서 찾는 열쇠가 각각의 경로를 탐색할 때 영향을 주고 있다는 것을 고려해야 하는 점이었다.
  • 즉, 1번 경로로 갔을 때 문 A를 열 수 있는 열쇠가 없어서 경로 탐색을 중지하고, 2번 경로에서 열쇠 a를 획득할 수 있는 경우 1번 경로에서 문 A를 연 이후의 경로도 탐색할 수 있다.
• 처음에 생각했던 방법은 다음과 같다.
  • 모든 입구에서 BFS를 적용해 현재 가지고 있는 열쇠를 가지고 탐색을 진행하고, 획득 가능한 열쇠를 모두 구한다.
  • 새롭게 획득한 열쇠를 적용하여 열 수 있는 문을 모두 빈칸(.)으로 처리한다.
  • 위 과정을 새로운 열쇠가 발견되지 않을 때까지 반복한다.
• 위 방법은 무조건 시간초과에 걸릴 것이고, BFS를 적용하는 입구가 순차적으로 결정되기 때문에 정확한 탐색을 진행할 수 있다고 판단하기 어렵다.
• 다른 문제 접근 방법
  • BFS는 단 한번의 호출로 끝낸다.
    • 주어진 지도를 감싸는 형태로 새로운 지도를 정의한다.

    • .	.	.	.
      .	o	o	.
      .	o	o	.
      .	.	.	.

    • 위 모습처럼 o 로 표시된 칸은 실제로 문제에서 주어지는 지도이고, 그 지도를 . 빈칸으로 감싼다.
    • 위 방법으로 하면 (0,0)에서 BFS 호출로 탐색을 시작하면 모든 입구에 대해 들어갈지 말지를 결정할 수 있다.
  • BFS 탐색을 위한 큐와 열쇠가 없어서 방문하지 못한 문의 좌표를 담는 큐 두가지를 선언한다.
    • queue<pair<int, int>> bfsQ, queue<pair<int, int>> door[26]
    • door 배열은 인접리스트 형태로 A~Z 에 각각 0~25 인덱스를 할당하고, 문을 열지 못한 경우 해당 자리에 좌표를 넣어둔다.
    • .,$, 열쇠가 있어서 문을 열 수 있는 경우는 bfsQ 에 담아 탐색을 계속하고, 열쇠가 없어서 문을 못여는 경우는 door 에 담는다.
    • 열쇠를 줍는 경우 door에서 해당 열쇠로 열 수 있는 문의 좌표들을 모두 bfsQ에 담아서 탐색 경로에 추가한다.
  • 훔쳐야 하는 문서 $를 만난 경우 이미 문서를 훔친 경우도 고려해야 하므로 훔친 문서의 좌표를 배열 checked[102][102] 에 체크해둔다.

구현

#include <iostream>
#include <string>
#include <vector>
#include <memory.h>
#include <queue>
#include <cctype>
using namespace std;

int H, W;
vector<string> board;
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
bool keys[26];
bool checked[102][102]; // 이미 획득한 $ 인지 확인
int ans = 0;

void printBoard() {
	cout << "------------------------\n";
	for (auto ele : board) {
		cout << ele << endl;
	}
}

void bfs(int sx, int sy) {
	// 열쇠가 없어서 열지 못한 문의 좌표를 담는다.
	// door[0][idx].first, door[0][idx].second 는 열지 못한 idx번 문 A의 좌표를 담는다.
	queue<pair<int, int>> door[26]; // 인접리스트 형태
	queue<pair<int, int>> q;
	bool visited[102][102];
	memset(visited, false, sizeof(visited));
	q.push(make_pair(sx, sy));
	visited[sx][sy] = true;

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

		for (int dir = 0; dir < 4; dir++) {
			int nx = cpos.first + dx[dir];
			int ny = cpos.second + dy[dir];
			if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
			if (board[nx][ny] == '*') continue;
			if (visited[nx][ny]) continue;
			// 문을 만난 경우
			if (isupper(board[nx][ny])) {
				// 열쇠가 있어서 열 수 있는 경우
				char ch = tolower(board[nx][ny]);
				if (keys[ch - 'a']) {
					visited[nx][ny] = true;
					q.push(make_pair(nx, ny));
				}
				// 열쇠가 없어서 열 수 없는 경우
				else {
					door[board[nx][ny] - 'A'].push(make_pair(nx, ny));
				}
			}
			// 열쇠를 주운 경우
			else if (islower(board[nx][ny])) {
				int idx = board[nx][ny] - 'a';
				keys[idx] = true;
				visited[nx][ny] = true;
				q.push(make_pair(nx, ny));
				// 이전에 열지 못한 문이 있는 경우 bfs 큐에 넣어서 다시 탐색할 수 있도록 한다.
				while (!door[idx].empty()) {
					q.push(door[idx].front());
					door[idx].pop();
				}
			}
			// 문서를 훔친 경우
			else if (board[nx][ny] == '$') {
				checked[nx][ny] = true;
				ans++;
				visited[nx][ny] = true;
				q.push(make_pair(nx, ny));
			}
			else if (board[nx][ny] == '.') {
				visited[nx][ny] = true;
				q.push(make_pair(nx, ny));
			}
		}
	}
}

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

	for (int test_case = 0; test_case < T; test_case++) {
		int h, w;
		cin >> h >> w;
		H = h + 2, W = w + 2;
		board.clear();
		memset(keys, false, sizeof(keys));
		memset(checked, false, sizeof(checked));
		ans = 0;
		board.push_back(string(W, '.'));
		string str;
		for (int i = 0; i < h; i++) {
			cin >> str;
			str.push_back('.');
			str.insert(str.begin(), '.');
			board.push_back(str);
		}
		board.push_back(string(W, '.'));

		// input key
		cin >> str;
		if (str != "0") {
			for (auto ele : str) {
				keys[ele - 'a'] = true;
			}
		}
		// printBoard();

		// 모든 입구에 대해서 bfs
		bfs(0, 0);
		printf("%d\n", ans);
	}
	return 0;
}