[백준] 9328번 열쇠

9328 열쇠

문제

---

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

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

입력

---

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

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

'.'는 빈 공간을 나타낸다

'*'는 벽을 나타내며, 상근이는 벽을 통과할 수 없다.

'$'는 상근이가 훔쳐야하는 문서이다

알파벳 대문자는 문을 나타낸다

알파벳 소문자는 열쇠를 나타내며, 그 문자의 대문자인 모든 문을 열 수 있다.

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

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

출력

---

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

---

풀이)

탐색 중에 새로운 열쇠를 얻으면 이전에 방문했지만 통과하지 못한 문을 통과할 수 있게끔 해줘야하는 문제였다.

그냥 열쇠 개수대로 방문표시 했을 때에는 시간초과가 났다.

(visited[102][102][26] 으로 방문체크했을 경우)

같을 곳을 20번도 넘게 방문할 가능성이 있어서 그런듯 하다.

또 옛날에 1194번 달이 차오른다 가자 문제처럼(https://comyoung.tistory.com/49)

방문 표시를 bit-masking을 통해 풀어볼까 했지만, 열쇠가 a ~ z 까지 26개라서 그러지 못했다.

그래서 다른 방법을 사용해서 풀었다.

통과하지 못한 문의 위치를 저장해놓고, 새로운 열쇠를 찾을 때마다 통과하지 못한 문과 일치한 열쇠인지

확인 후 일치할 경우 그 문의 위치를 queue에 삽입해 그 위치부터 다시 탐색하게 두었다.

이렇게 하니, 열쇠를 새로 얻게 된 후 이전에 방문했던 곳을 다시 방문해야 할 필요가 없어졌다.

과정은 이러하다

1. 맵의 주위를 '.'으로 둘러싼다. 

   이는 상근이가 빌딩 가장자리의 빈 공간이나 문을 통해 안팎을 드다닐 수 있기 때문에

   초반에 상근이가 빌딩에 들어갈 수 있는 위치를 queue에 모두 삽입하기 위해서이다.

2. BFS를 통해 상근이를 탐색시킨다.

 2.1 빈 공간일 경우 -> 그대로 탐색

 2.2 열쇠일 경우 -> 열쇠 소유 표시를 해주고, 이전에 통과하지 못한 문들을 확인. 

                         만일, 통과하지 못했던 문과 새로 얻은 열쇠가 일치할 경우 그 문의 위치를 queue에 삽입해 탐색

 2.3 문일 경우 -> 문과 일치하는 열쇠를 가졌으면 그대로 탐색

 열쇠를 가지지 못했으면 통과하지 못하므로 문의 위치 저장

 2.4 문서일 경우 -> 획득표시를 한 후(map의 값을 '.' 빈공간으로 바꿈), 얻은 문서 수 +1

3. 얻은 문서 수를 출력

주의사항

test_case 끝날때마다, 방문처리 저장하는 배열과 key 소유 표시하는 배열 초기화 필수

코드)

#include <stdio.h>
#include <queue>
#include <vector>
#include <string.h>
using namespace std;
 
struct Info {
    int y, x, num;
    Info(int y, int x) {
        this->y = y;
        this->x = x;
    }
};
 
int test_case, h, w;
char map[102][102];
bool key[26];
int result = 0; //훔친 문서수
bool visited[102][102];
vector<Info> door;//열리지 않은 문
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
void bfs(int a,int b) {
    queue<Info> qu;
    qu.push({ a,b });
    visited[a][b] = true;
    
    while (!qu.empty())
    {
        int y = qu.front().y;
        int x = qu.front().x;
        qu.pop();
        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (ny < 0 || ny > h +1 || nx < 0 || nx > w+1) continue;
            if (map[ny][nx] == '*' || visited[ny][nx]) continue;
            if (map[ny][nx] == '.') {
                visited[ny][nx] = true;
                qu.push({ ny,nx });
            }
            else if ('a' <= map[ny][nx] && map[ny][nx] <= 'z') {
                visited[ny][nx] = true;
                key[map[ny][nx] - 'a'] = true;
                qu.push({ ny,nx});
                for (int i = 0; i < door.size(); i++) {
                    if (door[i].y == -1) continue;
                    if (key[map[door[i].y][door[i].x] - 'A']) {
                        qu.push({ door[i].y, door[i].x });
                        visited[door[i].y][door[i].x] = true;
                        door[i].y = -1;
                    }
                }
            }
            else if ('A' <= map[ny][nx] && map[ny][nx] <= 'Z') {
                if (key[map[ny][nx] - 'A']) {
                    visited[ny][nx] = true;
                    qu.push({ ny,nx });
                }
                else {//열쇠없음 -> 나중에 열쇠생기고 다시 방문할수 있으므로 저장
                    door.push_back({ ny,nx });
                }
            }
            else { //문서일경우
                result++;
                visited[ny][nx] = true;
                qu.push({ ny,nx});
            }
            
        }
    }
}
int main() {
    scanf("%d", &test_case);
    while (test_case--)
    {
        scanf("%d %d", &h, &w);
        getchar();
        memset(map, '.', sizeof(map));
        for (int i = 1; i <= h; i++) {
            for (int j = 1; j <= w; j++) {
                scanf("%c", &map[i][j]);
            }
            getchar();
        }
        while (true)
        {
            char ch;
            scanf("%c", &ch);
            if (ch == '\n' || ch == '0') break;
            key[ch - 'a'] = true;
        }
 
        //상근이는 처음에는 빌딩 밖에 있고 빌딩 가장자리의 빈 공간이나 문을 통해
        //안팎을 드나듬
        bfs(0, 0);
 
        printf("%d\n", result);
 
        //다음 testcase를 위해 초기화
        result = 0;
        door.clear();
        memset(visited, false, sizeof(visited));
        memset(key, false, sizeof(key));
    }
    return 0;
}