열쇠(BOJ9328)

문제

이미지 클릭

문제 설명

• 기본적으로 맵의 구성은 다음과 같이 설명할 수 있다.

'.' :이동 가능한 빈 공간
'*': 이동 불가능한 벽
'$': 훔쳐야 하는 문서
알파벳 대문자: 문
알파벳 소문자: 열쇠(알파벳 대문자와 동일 문자일 경우 가능(a열쇠는 A문에서 가능))

• 맵이 주어진 다음에는 일련의 문자열이 주어지는데 이는 이미 가지고 있는 열쇠를 의미한다.
• 만약 0이 주어진다면 초기에 가지고 있는 열쇠는 없다.

cz: c와 z열쇠를 가지고 있음
0: 열쇠 없음

• 맵이 주어졌을 때 총 몇 개의 문서를 훔칠 수 있을지 알아내야 한다.

문제 해설

• bfs

일단 정점을 돌아보면서 다음과 같은 경우의 수를 모두 확인해 준다.
1. '.'인 경우: 그냥 이동
2. '$'인 경우: 문서의 개수를 +1해 주고 그 위치를 '.'으로 변경해 준다.
3. 대문자 알파벳인 경우: 열쇠가 있는 경우에는 그 위치로 이동해 준다.
4. 소문자 알파벳인 경우
-일단 열쇠가 없다면 열쇠를 체크해 주고, 현재까지 이동하면서 방문처리해 준 배열을 초기화해준다.(방문처리하면서 현제 열쇠와 알맞은 문을 방문했을 수도 있음)
-그리고 queue를 초기화해 주고 현제 위치부터 다시 탐색을 시작해 줌.

• 위의 부분만 만족해 주면서 bfs탐색을 해주면 깔끔하게 가능하다.

최종코드

#include <bits/stdc++.h>
using namespace std;
int t;
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
int main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        vector<bool> key(30, 0); #키 a~z를 0~25로 저장해준다.
        vector<vector<char>> c(n + 4, vector<char>(m + 4, '.'));
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                cin >> c[i][j];
            }
        }
        string s;
        cin >> s;
        if (s != "0") for (auto i : s) key[i - 'a'] = 1; 
        queue<pair<int, int>> q;
        vector<vector<int>> visited(n + 2, vector<int>(m + 2, 0)); 
        #건물 외부로도 이동가능하기 때문에 크기를 n+2, m+2로 설정해준다.
        q.push({0, 0}); 
        visited[0][0] = 1;
        int cnt = 0; #훔친문서의 개수
        while (!q.empty()) {
            int x = q.front().first, y = q.front().second;
            q.pop();
            for (int i = 0; i < 4; i++) {
                int xx = x + dx[i], yy = y + dy[i];
                if (xx >= 0 && yy >= 0 && xx <= n + 1 && yy <= m + 1 && !visited[xx][yy]) {
                    char cell = c[xx][yy];
                    if (cell == '*') continue;
                    visited[xx][yy] = 1;
                    if (cell == '.') { #빈칸이면 이동한다.
                        q.push({xx, yy}); 
                    } else if (cell == '$') {
                    #문서가 있으면 cnt+=1 해주고 현제 위치는 '.'으로 바꿔줌
                        cnt+=1;    
                        c[xx][yy] = '.'; 
                        q.push({xx, yy});
                    } else if (cell >= 'A' && cell <= 'Z') {
                        if (key[cell - 'A']) {
                        #현제 위치가 문이고 열쇠가 있다면 이동한다.
                            q.push({xx, yy});
                        }
                    } else if (cell >= 'a' && cell <= 'z') { 
                        if (!key[cell - 'a']) {
                            key[cell - 'a'] = 1; #열쇠 체크
                            fill(visited.begin(), visited.end(), vector<int>(m + 2, 0));
                            q = queue<pair<int, int>>();
                            #방문처리(visited)와 queue를 초기화해준다.
                        }
                        c[xx][yy] = '.';
                        q.push({xx, yy});
                    }
                }
            }
        }
        cout << cnt << "\n"; 
    }
}

이미지 클릭