🔍 9328 열쇠
상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 필요하다. 상근이는 일부 열쇠를 이미 가지고 있고, 일부 열쇠는 빌딩의 바닥에 놓여져 있다. 상근이는 상하좌우로만 이동할 수 있다.
상근이가 훔칠 수 있는 문서의 최대 개수를 구하는 프로그램을 작성하시오.
각 테스트 케이스의 첫째 줄에는 지도의 높이와 너비 h와 w (2 ≤ h, w ≤ 100)가 주어진다. 다음 h개 줄에는 빌딩을 나타내는 w개의 문자가 주어지며, 각 문자는 다음 중 하나이다.
'.'는 빈 공간을 나타낸다.
'*'는 벽을 나타내며, 상근이는 벽을 통과할 수 없다.
'$'는 상근이가 훔쳐야하는 문서이다.
알파벳 대문자는 문을 나타낸다.
알파벳 소문자는 열쇠를 나타내며, 그 문자의 대문자인 모든 문을 열 수 있다.마지막 줄에는 상근이가 이미 가지고 있는 열쇠가 공백없이 주어진다. 만약, 열쇠를 하나도 가지고 있지 않는 경우에는 "0"이 주어진다.
상근이는 처음에는 빌딩의 밖에 있으며, 빌딩 가장자리의 벽이 아닌 곳을 통해 빌딩 안팎을 드나들 수 있다. 각각의 문에 대해서, 그 문을 열 수 있는 열쇠의 개수는 0개, 1개, 또는 그 이상이고, 각각의 열쇠에 대해서, 그 열쇠로 열 수 있는 문의 개수도 0개, 1개, 또는 그 이상이다. 열쇠는 여러 번 사용할 수 있다.
🤔 풀이
- 빌딩의 밖에서 빌딩 입구를 찾는 법 : 입력받은 지도보다 두 줄 더 많은 행과 열을 가진 배열을 만든다. 지도는 배열의 중앙에 위치한다. 그리고 (0, 0) 부터 탐색을 시작한다면 빌딩의 모든 입구를 탐색할 수 있다.
- 현재 상근이가 무슨 키를 지니고 있는지 확인하는 방법이 필요하다. 따라서 입력받은 키를 인덱스로 하는 배열로 관리한다.
- 문을 만났을 때, 현재 열쇠가 없어 열지 못 하더라도 추후 열쇠를 얻으면 열 수 있다. 따라서 새로운 열쇠를 얻었을 때 해당 열쇠가 이전에 만났지만 열지못했던 문의 열쇠라면 해당 문의 위치로 돌아가 추가적으로 탐색을 진행하면 된다. → 문의 위치를 담을 큐를 사용한다. 이 큐는 각 문마다 하나씩 존재한다.
- 탐색을 위해 BFS방식을 사용한다. 다음 방문할 위치를 담은 큐(이동큐)에서 하나씩 꺼내며 탐색을 진행한다. 처음에는 (0, 0) 부터 큐에 넣고, 방문한 위치에는 visit을 표시한다. 큐에서 하나의 위치를 꺼낸 뒤 상하좌우 이동할 곳을 찾는다.
- 만약 방문한 적이 없는 위치이고, 해당 위치에 아무것도 없다면 이동큐에 추가한다.
- 만약 방문한 적이 없는 위치지만, 해당 위치에 벽이 있다면 visit을 표시하고 넘어간다.
- 만약 방문한 적이 없는 위치이고, 해당 위치에 문이 있다면 visit을 표시하고 키가 있는지 확인한다. 만약 키가 없다면 해당 문의 큐에 해당 위치를 넣는다. 만약 키가 있다면 다음으로 진행할 수 있다는 뜻이므로 이동큐에 위치를 넣는다.
- 만약 방문한 적이 없는 위치이고, 해당 위치에 키가 있다면 visit을 표시하고 이동큐에 위치를 넣는다. 그리고 만약 그 키가 새로 얻은 키라면, 해당 키로 열 수 있는 이전에 만난 문들의 위치를 이동큐에 추가한다.
- 만약 방문한 적이 없는 위치이고, 해당 위치에 문서가 있다면 이동큐에 추가하고, 문서 정답 수를 카운트한다.
📝 코드
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int h, w;
char board[102][102];
int keys[26];
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };
int ans;
int visiting[102][102];
void initial() {
fill(&visiting[0][0], &visiting[0][0]+10404, 0);
fill(&board[0][0], &board[0][0]+10404, 0);
fill(keys, keys+26, 0);
ans = 0;
}
int inRange(int x, int y) {
return x >= 0 && x <= h+1 && y >= 0 && y <= w+1;
}
void adven(int x, int y) {
queue<pair<int, int> > que;
queue<pair<int, int> > door[26];
visiting[x][y] = 1;
que.push(make_pair(x, y));
while (!que.empty()) {
int nx = que.front().first;
int ny = que.front().second;
que.pop();
for (int i = 0; i < 4; i++) {
int nnx = nx+dx[i];
int nny = ny+dy[i];
if (inRange(nnx, nny) && !visiting[nnx][nny]) {
visiting[nnx][nny] = 1;
if (board[nnx][nny] == '*') continue;
if (board[nnx][nny] >= 'A' && board[nnx][nny] <= 'Z') {
if (keys[board[nnx][nny]-'A']) { // 키가 있다.
que.push(make_pair(nnx, nny));
}
else {
door[board[nnx][nny]-'A'].push(make_pair(nnx, nny));
}
}
else if (board[nnx][nny] >= 'a' && board[nnx][nny] <= 'z') {
que.push(make_pair(nnx, nny));
if (!keys[board[nnx][nny]-'a']) { // 키가 원래 없었다.
keys[board[nnx][nny]-'a'] = 1;
while (!door[board[nnx][nny]-'a'].empty()) {
que.push(door[board[nnx][nny]-'a'].front());
door[board[nnx][nny]-'a'].pop();
}
}
}
else {
que.push(make_pair(nnx, nny));
if (board[nnx][nny] == '$') ans++;
}
}
}
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int T;
cin >> T;
while (T--) {
initial();
cin >> h >> w;
for (int i = 1; i <= h; i++) {
for (int j = 1; j <= w; j++) {
cin >> board[i][j];
}
}
string s;
cin >> s;
for (int i = 0; i < s.length(); i++) {
if (s[i] == '0') break;
keys[s[i]-'a'] = 1;
}
adven(0, 0);
cout << ans << endl;
}
}