[백준 9328] 열쇠

[백준 9328] 열쇠

문제 링크

#include "header"
using namespace std;
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
int visit[101][101];
char maze[101][101];
int keys[130];  //97~122 소문자 알파벳
int t, ans, h, w;
vector<pair<int, int>> v;

void bfs() {
    int j = 0;
    for (j = 0; j < v.size(); j++) {
        queue<pair<int, int>> q;
        
        if(isupper(maze[v[j].first][v[j].second])){
            int cmp = tolower(maze[v[j].first][v[j].second]);
            if(!keys[cmp]) continue;
            else maze[v[j].first][v[j].second] = '.';
        }

        q.push({v[j].first, v[j].second});
        
        while (!q.empty()) {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
            visit[x][y] = 1;

            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if (visit[nx][ny] || maze[nx][ny] == '*' || nx < 0 || ny < 0 || nx >= h || ny >= w)
                    continue;

                int cmp = tolower(maze[nx][ny]);
                if (isupper(maze[nx][ny])) {  //door
                    if (keys[cmp]) maze[nx][ny] = '.'; //열쇠가 있으면
                    else continue;                     //열쇠가 없으면
                } else if (islower(maze[nx][ny])) {  //key
                    if (keys[cmp]) maze[nx][ny] = '.'; //이미 가진 열쇠라면
                    else {                             //새로운 열쇠라면
                        keys[cmp] = 1;
                        maze[nx][ny] = '.';
                        j = -1; //처음부터 탐색
                        memset(visit, 0, sizeof(visit));
                    }
                } else if (maze[nx][ny] == '$') { //문서라면
                    ans++;
                    maze[nx][ny] = '.';
                }

                visit[nx][ny] = 1;
                q.push({nx, ny});
            }
        }
    }
}
void solve() {
    //가생이 돌기
    for (int i = 0; i < h; i++) {
        int cmp = tolower(maze[i][0]);
        if (maze[i][0] != '*'){
            if (islower(maze[i][0])) {  //key
                if (!keys[cmp]) keys[cmp] = 1;
            } else if (maze[i][0] == '$') {
                ans++;
                maze[i][0] = '.';
            }
            v.push_back({i, 0});
        }
    }

    for (int i = 0; i < w; i++) {
        int cmp = tolower(maze[0][i]);
        if (maze[0][i] != '*'){
            if (islower(maze[0][i])) {  //key
                if (!keys[cmp]) keys[cmp] = 1;
            } else if (maze[0][i] == '$') {
                ans++;
                maze[0][i] = '.';
            }
            v.push_back({0, i});
        }
    }

    int n = w - 1;
    for (int i = 0; i < h; i++) {
        int cmp = tolower(maze[i][n]);
        if (maze[i][n] != '*'){
            if (islower(maze[i][n])) {  //key
                if (!keys[cmp]) keys[cmp] = 1;
            } else if (maze[i][n] == '$') {
                ans++;
                maze[i][n] = '.';
            }
            v.push_back({i, n});

        }
    }

    n = h - 1;
    for (int i = 0; i < w; i++) {
        int cmp = tolower(maze[n][i]);
        if (maze[n][i] != '*'){
            if (islower(maze[n][i])) {  //key
                if (!keys[cmp]) keys[cmp] = 1;
            } else if (maze[n][i] == '$') {
                ans++;
                maze[n][i] = '.';
            }
            v.push_back({n, i});

        }
    }
}
void input() {
    vector<int> answer;
    cin >> t;

    for (int k = 0; k < t; k++) {
        cin >> h >> w;
        ans = 0;
        memset(visit, 0, sizeof(visit));
        memset(keys, 0, sizeof(keys));
        memset(maze, 0, sizeof(maze));
        v.clear();

        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                cin >> maze[i][j];
            }
        }

        string key;
        cin >> key;
        if (key != "0") {
            for (int j = 0; j < key.length(); j++) {
                int key_ = key[j];
                keys[key_] = 1;
            }
        }
        solve();
        bfs();

        answer.push_back(ans);
    }

    for (auto a : answer) {
        cout << a << endl;
    }
}
int main() {
    input();
    return 0;
}

• 완전 더럽게 풀었다.
• 1. 가장자리를 돌면서 들어갈 수 있는 곳을 벡터에 모두 넣는다.
     • 이 때, 문서라면 답을 +1 해 주고, 빈 칸으로 바꿔놓는다.
     • 열쇠라면 줍고, 배열에 표시 해 준 후, 빈 칸으로 바꿔놓는다.
• 1. 벡터를 돌면서 bfs를 돈다.
     • 만약 문이라면
       • 키가 있다면 문을 연다. 문을 빈 칸으로 바꾼다.
       • 키가 없다면 continue
     • 만약 문서라면
       • 답 +1 후 빈 칸으로 바꾼다.
     • 만약 열쇠라면
       • 벡터를 처음부터 돌기 위해 j를 -1로 바꿔준다.
       • visit 배열을 초기화 시켜준다.