열쇠

백준 9328번: 열쇠

아이디어

우선 거리를 재는 문제가 아니기 때문에 열쇠 보유 상황에 따라 다른 배열을 사용할 필요는 없다. visited 배열에 현재 열쇠 상태를 기록한다. 이전과 다른 열쇠 보유 상황이면(열쇠 하나라도 새로 주웠으면) 다시 탐색한다.
열쇠 보유 상황은 a부터 z까지 1<<26 으로 나타내면 int에 충분히 담을 수 있다.

코드

#include <bits/stdc++.h>

using namespace std;

typedef struct _data {
    int y, x;
} Data;

int T, N, M;
const int dy[4] = {1, -1, 0, 0};
const int dx[4] = {0, 0, 1, -1};
char m[100][100];
int visited[100][100];

int solve(vector<pair<int, int>> ent, int key) {
    if (ent.empty()) return 0;
    int ret = 0;
    queue<Data> q;
    q.push({-10, -10});
    while (!q.empty()) {
        int y = q.front().y;
        int x = q.front().x;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
            if (m[ny][nx] == '*') continue;
            if (visited[ny][nx] == key) continue;
            
            if (m[ny][nx] >= 'a' && m[ny][nx] <= 'z') {
                if (!(key&1<<m[ny][nx]-'a')) {
                    memset(visited, 0, sizeof(visited));
                }
                visited[ny][nx] = key;
                q.push({ny, nx});
                key = key|(1<<m[ny][nx]-'a');
            }
            else if (m[ny][nx] >= 'A' && m[ny][nx] <= 'Z') {
                if (key&(1<<m[ny][nx]-'A')) {
                    visited[ny][nx] = key;
                    q.push({ny, nx});
                }
            }
            else if (m[ny][nx] == '$') {
                ret += 1;
                m[ny][nx] = '.';
                visited[ny][nx] = key;
                q.push({ny, nx});
            }
            else {
                visited[ny][nx] = key;
                q.push({ny, nx});
            }
        }
        for (auto p : ent) {
            int ny = p.first;
            int nx = p.second;
            
            if (visited[ny][nx] == key) continue;
            
            if (m[ny][nx] >= 'a' && m[ny][nx] <= 'z') {
                if (!(key&1<<m[ny][nx]-'a')) {
                    memset(visited, 0, sizeof(visited));
                }
                visited[ny][nx] = key;
                q.push({ny, nx});
                key = key|(1<<m[ny][nx]-'a');
            }
            else if (m[ny][nx] >= 'A' && m[ny][nx] <= 'Z') {
                if (key&(1<<m[ny][nx]-'A')) {
                    visited[ny][nx] = key;
                    q.push({ny, nx});
                }
            }
            else if (m[ny][nx] == '$') {
                ret += 1;
                m[ny][nx] = '.';
                visited[ny][nx] = key;
                q.push({ny, nx});
            }
            else {
                visited[ny][nx] = key;
                q.push({ny, nx});
            }
            
        }
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> T;
    while (T--) {
        memset(visited, -1, sizeof(visited));
        vector<pair<int, int>> v;
        cin >> N >> M;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                cin >> m[i][j];
                if (i == 0 || i == N-1 || j == 0 || j == M-1) {
                    if (m[i][j] != '*') {
                        v.push_back({i, j});
                    }
                }
            }
        }
        int k = 0;
        string s;
        cin >> s;
        for (char x : s) {
            if (x != '0') {
                k = k|(1<<(x-'a'));
            }
        }
        cout << solve(v, k) << '\n';
        memset(m, 0, sizeof(m));
        memset(visited, -1, sizeof(visited));
    }
    return 0;
}

여담

고려해야 할게 좀 많았다. 우선 테두리의 어느 곳이라도 즉시 이동이 가능하다라는 점 때문에 상하좌우 네 방향과 테두리까지 전부 검사하여 이전과 다른 열쇠 상태가 기록된 곳을 탐색해야 한다.
또 열쇠가 하나도 없는 상태를 0으로 설정했기 때문에 visited의 초깃값을 0으로 설정하면 제대로 작동하지 않는다. -1로 설정하면 잘 작동한다.