BOJ_9328 열쇠 C++

HDuckkk·2023년 7월 25일

Beakjoon Online Judge

목록 보기

11/13

BOJ_9328 열쇠 C++

문제

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

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

문제 풀이

상근이가 문서를 훔쳐온단다. ~~성심성의껏~~ 도와주도록 하자.

나는 BFS를 이용한 접근방법을 사용했다.

여기서 문제가 각 열쇠마다 열 수 있는 문이 정해져있으며 하나의 열쇠는 다수의 문을 열 수 있다고 한다.

~~무지성~~ 시뮬레이션을 구현하면 상근이가 열쇠 들고 문따러다니다가 동선 꼬이면 시간초과 날 것 같아서 고민을 좀 해야했다.

결과적으로 문이나 열쇠를 발견할 때 마다 특정한 행동을 하면 BFS를 이용한 한번의 탐색으로 문제 해결이 가능하다.

특정한 행동에 대해 알아보자.

문을 발견했을 때
- 찾았던 열쇠를 뒤져본다.
  - 있다면, 문을 열고 들어간다.
  - 없다면, 문의 위치와 정보를 기억한다.
열쇠를 발견했을 때
- 찾았던 문을 뒤져본다.
  - 열 수 있는 문이 있다면, 그 문을 연 뒤 큐나 스택에 넣어두어 탐색을 보장한다.
  - 찾은 열쇠를 목록에 추가한다.

크게 두가지 상황에서의 동작을 통해 우리는 한번의 BFS를 통해 문제 해결이 가능해진다.

그림으로 확인해보자.

다음과 같은 상황이 있다고 하자.

여기서 검은색 바탕은 벽이며 각 색깔별 열쇠와 문은 각각 짝이되는 열쇠와 문이라 하자.

여기서 ~~무지성~~ 시뮬레이션을 구현해버리면 방향성도 찾기 어려울 것이며 탐색했다는 흔적을 남기기에도 많이 까다로울 것이다.

이때 위에서 서술한 두가지 특정한 행동을 이용하면 다음과 같을 것이다.

우선 BFS를 활용하니 가까이 있는 파란색 열쇠를 먼저 찾을것이다.

열쇠를 발견했을 때 찾은 문 목록을 뒤져보니 아무것도 나오지 않을 것이다.

이런 경우에는 찾은 열쇠목록만 활성화 해 준 뒤 마저 BFS를 진행한다.

이후 두번째로 파란색 문을 발견할 것이다.

이 때 찾은 열쇠 목록을 뒤져보니 파란색 열쇠가 있으므로 문을 열고 탐색을 계속한다.

이후의 상황은 다음과 같을 것이다.

갈색 문을 먼저 탐색해 두었다고 생각해보자.

갈색 문을 찾았으나 갈색 열쇠가 없기에 찾은 문 목록에 추가만 해둔 뒤 마저 탐색을 이어간다.

이후 갈색 열쇠를 찾았다고 하면 찾은 문 목록을 뒤며본다.

이때 갈색 문을 찾았던 기억을 하고 있으니 해당 문의 위치를 큐나 스택에 추가해 탐색을 보장한다.

결과적으로는 열수 있는 모든 문을 연채 상근이가 챙길 수 있는 문서는 전부 챙길 것이다.

코드

// BOJ 9328
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <string>
using namespace std;
using pii = pair<int, int>;

struct door{
    char num;
    pii loc;
    bool opened = false;
};


int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};
vector<door> vec;
char map[100][100];
bool vis[100][100];
bool key[128];

int H, W;

void printMap(){
    cout << "print Map\n";
    for(int i=0; i<H; i++){
        for(int j=0; j<W; j++){
            cout << map[i][j] << " ";
        }
        cout << "\n";
    }
}

void printDoor(){
    cout << "print Door\n";
    for(int i=0; i<vec.size(); i++){
        cout << vec[i].num << " : {" << vec[i].loc.second << ", " << vec[i].loc.second << "} opened ? " << vec[i].opened << "\n";
    }
}

void init(){
    cin >> H >> W;
    for(int i=0; i<H; i++){
        string temp;
        cin >> temp;
        for(int j=0; j<W; j++){
            map[i][j] = temp[j];
        }
    }

    string tempKey;
    cin >> tempKey;

    if(tempKey == "0") return;

    for(int i=0; i<tempKey.size(); i++){
        key[tempKey[i]] = true;
    }
}

void BFS(){
    queue<pii> q;
    int ANS = 0;
    
    for(int i=0; i<H; i++){
        if(i == 0 || i == H-1){
            for(int j=0; j<W; j++){
                if(map[i][j] == '*') continue;

                q.push({i,j});
            }
        }else{
            for(int j=0; j<2; j++){
                if(j == 0){
                    if(map[i][0] == '*') continue;

                    q.push({i,0});
                }else{
                    if(map[i][W-1] == '*') continue;

                    q.push({i,W-1});
                }
            }
        }
    }

    while (!q.empty()){
        int cur_y = q.front().first;
        int cur_x = q.front().second;
        q.pop();

        if(vis[cur_y][cur_x]) continue;

        /* find door */
        if(map[cur_y][cur_x] >= 65 && map[cur_y][cur_x] <= 90){
            bool flag = false;
            for(int i=0; i<vec.size(); i++){
                if(vec[i].loc.first == cur_y && vec[i].loc.second == cur_x && vec[i].num == map[cur_y][cur_x]){
                    flag = true;
                }
            }

            if(!flag){
                door d;
                d.loc = {cur_y, cur_x};
                d.num = map[cur_y][cur_x];
                d.opened = false;

                vec.push_back(d);
            }

            /* it has key? */
            if(!key[ map[cur_y][cur_x] + 32]) continue;

            for(int i=0; i<vec.size(); i++){
                if(vec[i].loc.first == cur_y && vec[i].loc.second == cur_x && vec[i].num == map[cur_y][cur_x]){
                    vec[i].opened = true;
                }
            }

            map[cur_y][cur_x] = '.';
        }

        /* find key */
        if(map[cur_y][cur_x] >= 97 && map[cur_y][cur_x] <= 122){
            key[map[cur_y][cur_x]] = true;

            /* we found door? */

            for(int i=0; i<vec.size(); i++){
                if(vec[i].opened || vec[i].num != map[cur_y][cur_x] - 32) continue;

                int temp_y = vec[i].loc.first;
                int temp_x = vec[i].loc.second;
             
                q.push({temp_y, temp_x});
            }

            map[cur_y][cur_x] = '.';
        }

        /* find paper */
        if(map[cur_y][cur_x] == '$'){
            ANS++;
            map[cur_y][cur_x] = '.';
        }

        vis[cur_y][cur_x] = true;


        for(int i=0; i<4; i++){
            int nex_y = cur_y + dy[i];
            int nex_x = cur_x + dx[i];

            if(nex_x < 0 || nex_y < 0 || nex_y >= H || nex_x >= W) continue;
            if(map[nex_y][nex_x] == '*') continue;
            if(vis[nex_y][nex_x]) continue;

            q.push({nex_y, nex_x});
        }
    }

    cout << ANS << "\n";
}

void _clear(){
    while (!vec.empty()){
        vec.pop_back();
    }

    for(int i=0; i<100; i++){
        memset(map[i], 0, sizeof(map[i]));
        memset(vis[i], 0, sizeof(vis[i]));
    }

    memset(key, 0, sizeof(key));
}

int main(){

    int testCase;
    cin >> testCase;

    while (testCase--){

        init();
        BFS();
        _clear();

    }

    return 0;
}