[백준 - 9328] 열쇠 - C++

분류: BFS /

 

문제

문제 링크

문제 설명

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

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

입력

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

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

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

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

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

출력

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

 

풀이

- 첫 풀이

#include <iostream>
#include <vector>
#include <string>
#include <queue>
using namespace std;

struct xy {int x, y;};
int mark, h, w;
string keys;
char board[100][100];
int vis[100][100];
vector<xy> doors[26];
bool open[26];
queue<xy> Q;
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

bool isDoor(char x) {return x >= 'A' and x <= 'Z';}
bool isKey(char x) {return x >= 'a' and x <= 'z';}
bool OOB(int x, int y) {return x<0 or x>=h or y<0 or y>=w;}
bool blocked(int x, int y) {
    if(OOB(x, y)) return true;
    if(board[x][y] == '*') return true;
    if(vis[x][y] == mark) return true;
    if(isDoor(board[x][y]) and not open[board[x][y] - 'A']) return true;
    return false;
}
void openDoor(char key) {
    open[key - 'a'] = true;
    auto &door = doors[key - 'a'];
    while(not door.empty()) {
        auto [x, y] = door.back(); door.pop_back();
        for(int dir=4; dir--;) {
            int nx = x + dx[dir], ny = y + dy[dir];
            if(OOB(nx, ny) || vis[nx][ny] == mark) {
                Q.push({x, y});
                break;
            }
        }
    }
}

void bfs(int &ans, int X, int Y) {
    Q.push({X, Y});
    vis[X][Y] = mark;
    while(not Q.empty()) {
        auto [x, y] = Q.front(); Q.pop();
        if(board[x][y] == '$') ans++;
        else if(isKey(board[x][y]) and not open[board[x][y] - 'a'])
            openDoor(board[x][y]);
        
        for(int dir=4; dir--;) {
            int nx = x + dx[dir], ny = y + dy[dir];
            if(blocked(nx, ny)) continue;
            vis[nx][ny] = mark;
            Q.push({nx ,ny});
        }
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> mark;
    while(mark) {
        for(int i=0; i<26; i++) {
            doors[i].clear();
            open[i] = false;
        }
        cin >> h >> w;
        for(int i=0; i<h; i++) {
            cin >> board[i];
            for(int j=0; j<w; j++)
                if(isDoor(board[i][j]))
                    doors[board[i][j] - 'A'].push_back({i, j});
        }
        cin >> keys;
        if(keys != "0")
            for(char key:keys)
                openDoor(key);
            
        int ans = 0, x = 0, y = 0, n = 2*(w+h)-4, dir = 0;
        while(n--) {
            if(not blocked(x, y))
                bfs(ans, x, y);

            int nx = x + dx[dir], ny = y + dy[dir];
            if(OOB(nx, 0)) y += dy[++dir];
            else if(OOB(0, ny)) x += dx[++dir];
            else {x = nx; y = ny;}
        }
        cout << ans << '\n';
        mark--;
    }
}

코드가 굉장히 긴데 주요 로직은 다음과 같다.

• 입력을 받으며 모든 문의 위치를 저장(`doors`)
• 키를 입력 받고 해당 키의 문을 모두 염(`openDoor`)
• (0,0) 부터 테두리를 돌며 들어갈 수 있다면 `bfs`를 수행(달팽이 수열)
  • `$`라면 답을 1 증가
  • 키를 발견하고 해당 키의 문이 아직 안열렸다면 해당 키의 모든 문을 염
    • 문을 열 때, 연 문이 지나친 문이거나 테두리에 있는 문이라면 큐에 삽입

`vis`는 다른 숫자로 마킹해 매 테스트 케이스마다 초기화 과정을 생략했다. (다른 값으로 방문 표시)

지나친 문을 열 경우 다시 큐에 삽입하는 것은 [백준 - 11967] 불켜기에서 고민했던 적이 있어 바로 구현할 수 있었다.

 

그 외에 볼만한 곳은 달팽이 수열로 테두리를 도는 부분 정도.

달팽이 수열로 테두리를 돌게하기 위해서는 `dx` `dy`의 순서도 잘 맞춰줘야한다.

 

- 다듬은 풀이

#include <iostream>
#include <queue>
#include <vector>
#include <string>
using namespace std;

struct xy {int x, y;};
char board[102][102];
int vis[102][102];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int mark; cin >> mark;
    while(mark) {
        int h, w, ans = 0;
        bool open[26] = {};
        vector<xy> locked[26];
        queue<xy> Q;

        cin >> h >> w;
        for(int i=1; i<=h; i++) cin >> (board[i] + 1);
        for(int i:{0, h+1}) 
            for(int j=0; j<w+2; j++)
                board[i][j] = '\0';
        for(int i=1; i<h; i++) 
            for(int j:{0, w+1})
                board[i][j] = '\0';
        string keystr; cin >> keystr;
        if(keystr != "0")
            for(char k:keystr) open[k - 'a'] = true;

        Q.push({0, 0});
        vis[0][0] = mark;
        while(!Q.empty()) {
            xy cur = Q.front(); Q.pop();
            for(int dir=4; dir--;) {
                int nx = cur.x + dx[dir], ny = cur.y + dy[dir];
                if(nx<0 || nx>(h+1) || ny<0 || ny>(w+1)) continue;
                if(board[nx][ny] == '*' || vis[nx][ny] == mark) continue;
                vis[nx][ny] = mark;
                if(board[nx][ny] >= 'A' && board[nx][ny] <= 'Z') {
                    int k = board[nx][ny] - 'A';
                    if(!open[k]) {
                        locked[k].push_back({nx, ny});
                        continue;
                    }
                }
                else if(board[nx][ny] >= 'a' && board[nx][ny] <= 'z') {
                    int k = board[nx][ny] - 'a';
                    open[k] = true;
                    while(!locked[k].empty()) {
                        Q.push(locked[k].back());
                        locked[k].pop_back();
                    }
                }
                else if(board[nx][ny] == '$') ans++;
                Q.push({nx, ny});
            }
        }
        cout << ans << '\n';
        mark--;
    }
}

# 지나친 문 처리

다른 사람의 풀이를 보며 알게된 부분인데 문을 열 때 문 주변에 방문한 곳을 찾아 지나친 문인지 확인하지 않고 지나칠 때 마다 저장하면된다.

이 방법이 지나친 문만 큐에 삽입할 지 고려하기 때문에 더 효율적이다.

• 키라면 문을 열고 지금까지 지나친 해당 문을 모두 BFS 큐에 삽입
• 문이고 아직 안열렸다면 따로 저장하고 패스

 

# 테두리 돌기

0행, h+1행, 0열, w+1열을 비워두고 (0,0)부터 bfs를 돌리면 알아서 테두리를 돌게된다. 

주의할 점은 이전 테스트케이스에서 `board`의 크기가 현재보다 크다면 테두리에 쓰레기값이 남아있어 매 테스트 케이스마다 테두리를 비워줘야한다.

전체 `board`를 비우는 것이 더 쉽긴하지만 테두리만 비우는 것이 더 효율적이다.

또 입력을 한칸 띄고 받아야 한다.(`cin >> (board[i] + 1)`)