[BFS] 9328번 열쇠

9328번 열쇠

 

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

 

문제

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

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

 

입력

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

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

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

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

상근이는 빌딩 밖으로 나갈 수 있다. 각각의 문에 대해서, 그 문을 열 수 있는 열쇠의 개수는 0개, 1개, 또는 그 이상이고, 각각의 열쇠에 대해서, 그 열쇠로 열 수 있는 문의 개수도 0개, 1개, 또는 그 이상이다. 열쇠는 여러 번 사용할 수 있다.

 

출력

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

 

예제 입력

3
5 17
*****************
.............**$*
*B*A*P*C**X*Y*.X.
*y*x*a*p**$*$**$*
*****************
cz
5 11
*.*********
*...*...*x*
*X*.*.*.*.*
*$*...*...*
***********
0
7 7
*ABCDE*
X.....F
W.$$$.G
V.$$$.H
U.$$$.J
T.....K
*SQPML*
irony

 

예제 출력

3
1
0

 

해결방법

정말 너~~무 어려웠다...

사실 이 문제는 예전에 봤다가 포기한 문제인데 달이 차오른다, 가자. 를 풀어보고 문제의 형태가 비슷해서 다시 도전해봤다

하지만 위의 문제는 열쇠의 가지수가 6개로 비트마스킹이 가능했는데, 이 문제는 열쇠의 가지수가 26개로 비트마스킹이 불가능하여 중복 방문에 대한 처리가 감이 안잡혔다

결국 구글링을 하여 솔루션을 참고하여 문제를 해결하였다

 

참고 블로그 : http://minemi.tistory.com/76

 

⭐️ 솔루션 ⭐️

 

1. 초기 입력

• 보유하고 있는 열쇠를 체크하기 위해 bool key[26] 배열을 선언한다

• 현재 보유하고 있는 열쇠를 돌며 배열에 체크해준다

 

2. 문을 만났을 경우

• 현재 가지고 있는 열쇠로 문을 열 수 있다면

  → 문의 좌표를 큐에 넣어서 BFS 탐색을 계속 수행한다

• 문을 열 수 있는 열쇠를 가지고 있지 않다면

  → 아직 열지 못한 문을 저장하는 벡터에 넣어준다

 

3. 열쇠를 만났을 경우

• key 배열에 해당 열쇠를 true 로 바꿔준다
• 대기 중인 문을 돌며 열쇠가 문에 일치한다면 해당 문의 좌표를 큐에 넣어서 탐색을 계속 수행한다
• 또한 열쇠의 좌표도 큐에 넣어 탐색을 진행한다

 

4. 문서를 만났을 경우 & 나머지 경우

• 문서를 만났으면 ans++ 을 수행해주고 계속 탐색을 수행한다
• 나머지 경우는 이동할 수 있는 노드이기 때문에 계속 탐색을 수행한다

 

 

 

소스코드

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <cstring>
#include <set>
#include <queue>
#include <vector>
#include <algorithm>
#define MAX 102
#define INF 987654321
using namespace std;

struct node {
    int x,y;
    
    node() { }
    node(int _x,int _y) : x(_x),y(_y) { }
};

int testcase;
int n,m,ans;
string input_key;

char map[MAX][MAX];
bool visited[MAX][MAX];
bool key[26];

int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};

vector<node> door;

void bfs(){
    queue<node> q;
    q.push(node(0,0));
    visited[0][0] = true;
    
    while(!q.empty()){
        int x = q.front().x;
        int y = q.front().y;
        q.pop();
        
        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx<0 || ny<0 || nx>n+1 || ny>m+1) continue;
            if(map[nx][ny] == '*') continue;
            if(visited[nx][ny]) continue;
            
            // 문을 만난 경우
            if(map[nx][ny]>='A' && map[nx][ny]<='Z'){
                int ind = map[nx][ny] - 'A';
                // 열쇠를 보유한 경우
                if(key[ind]){
                    q.push(node(nx,ny));
                    visited[nx][ny] = true;
                }
                // 열쇠가 없는 경우
                else{
                    door.push_back(node(nx,ny));
                }
            }
            // 열쇠를 만난 경우
            else if(map[nx][ny]>='a' && map[nx][ny]<='z'){
                int ind = map[nx][ny] - 'a';
                key[ind] = true;
                
                for(int i=0; i<door.size(); i++){
                    int px = door[i].x;
                    int py = door[i].y;
                    
                    if(px == -1 && py == -1) continue;
                    
                    if(ind == map[px][py]-'A'){
                        q.push(node(px,py));
                        visited[px][py] = true;
                        
                        door[i].x = -1;
                        door[i].y = -1;
                    }
                }
                
                q.push(node(nx,ny));
                visited[nx][ny] = true;
            }
            // 문서를 만난 경우
            else if(map[nx][ny] == '$'){
                ans++;
                q.push(node(nx,ny));
                visited[nx][ny] = true;
            }
            // 나머지 경우
            else{
                q.push(node(nx,ny));
                visited[nx][ny] = true;
            }
        }
    }
    door.clear();
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> testcase;
    for(int t=0; t<testcase; t++){
        memset(map, '.', sizeof(map));
        
        cin >> n >> m;
        for(int i=1; i<=n; i++){
            for(int j=1; j<=m; j++){
                cin >> map[i][j];
            }
        }
        
        memset(visited, false, sizeof(visited));
        memset(key, false, sizeof(key));
        
        // 현재 보유하고 있는 키를 입력
        cin >> input_key;
        if(input_key != "0"){
            for(int i=0; i<input_key.size(); i++){
                key[input_key[i]-'a'] = true;
            }
        }
        
        ans = 0;
        bfs();
        cout << ans << "\n";
    }
    
    return 0;
}