[백준][C++] 9328번: 열쇠 <228>

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

 

https://www.acmicpc.net/problem/9328

9328번: 열쇠

생각의 흐름

우선 이 문제를 가장 쉽게 해결하기 위해서는 지도의 태두리를 이동할수 있는 길('.') 로 만들어야 한다.

다음 그림을 살펴보자.

 

위 그림과 같이 초록색 부분이 원래의 MAP이고, 회색 영역이 우리가 추가해준 부분이다.

이는 외부에서 태두리를 통해서도 지도상으로 들어올 수 있기 때문에 사용하는 것 이다.

 

아니면 불편하게 isEntrance()와 같은 함수를 만들어서, 불편하게 직접 다 확인해야 한다.

원래 처음에는 태두리의 입구인지를 확인하는 위와 같은 코드를 만들어 사용했는데.....

그냥 간편하게 태두리를 한줄 만들어주면 편하개 해결할 수 있다.

 

▶ 문을 만났을 경우

문에 도착하면, 키가 있다면 열수있고, 아니라면 열수가 없다.

 

문을 열 수 있다면, 그대로 Queue에 넣어주고 계속 진행을 하면 된다.

만약 열 수 없는 문이라면, Queue에 담을 수 없을 것이고, 그 방향으로는 탐색이 더이상 불가능하다.

 

하지만, 나중에 key가 발견되면 열 수도 있는 문일 수도 있기 때문에 Queue에 저장해준다.

( 여기서 말하는 Queue가 현재 BFS를 진행하는 Queue가 아닌, 따로 하나 더 만들어놓은 Door[26] Queue를 의미한다. )

예를 들어 (a, b) 좌표에 있는 A라는 문을 현재 열 수 없다면, Door[A].push(a,b) 이런식으로 문의 좌표를 저장해준다.

 

▶ 열쇠를 만났을 경우

열쇠를 만났을 경우, 해당 열쇠를 이미 가지고 있다면 Queue에 넣어주고 계속 진행만 하면 된다.

하지만, 기존에 없었던 새로운 열쇠를 주웠다면, 주운 열쇠를 Key[] 배열로 주웠다는 표시를 먼저 해주자.

 

이후 이전에 Door[] 배열에 저장해 둔 배열에 접근하여, 해당 Door[]에 담겨있는 모든 원소를 추출한다.

새롭게 발견한 키로 열수있는 곳들인것 이다!

따라서 이 원소들을 Queue에 추가하여 이번에는 탐색을 할수 있도록 해주면 된다!

 

 

나의 코드

#include <bits/stdc++.h>
#include <iostream>

using namespace std;
#define MAX 102
#define INF 987654321

int T;
int h, w;
char MAP[MAX][MAX];
bool visited[MAX][MAX];
bool keySet[26];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int res;

void init() {
    memset(MAP, 0, sizeof(MAP));
    memset(visited, false, sizeof(visited));
    memset(keySet, false, sizeof(visited));
    res = 0;
}

void show(){
    for (int i = 0; i <= h+1; i++) {
        for (int j = 0; j <= w+1; j++) {
            cout << MAP[i][j] << " ";
        }
        cout << "\n";
    }
}

void searchMap(int x, int y) {
    queue<pair<int, int>> Q;
    queue<pair<int, int>> Door[26];
    Q.push({x, y});
    visited[x][y] = true;

    while (!Q.empty()) {
        int nowX = Q.front().first;
        int nowY = Q.front().second;
        Q.pop();

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

            if (nx < 0 || ny < 0 || nx > h+1 || ny > w+1) continue;
            // 이미 방문했거나, 벽인경우 제외
            if(MAP[nx][ny] == '*' || visited[nx][ny] == true) continue;

            visited[nx][ny] = true;
            if (MAP[nx][ny] >= 'A' && MAP[nx][ny] <= 'Z') { // 문인 경우
                if (keySet[MAP[nx][ny] - 'A'] == true) {
                    Q.push({nx, ny});
                } else {
                    Door[MAP[nx][ny] - 'A'].push({nx, ny});
                }
            } else if (MAP[nx][ny] >= 'a' && MAP[nx][ny] <= 'z') { // 열쇠인 경우
                Q.push({nx, ny});

                if(keySet[MAP[nx][ny] - 'a'] == false) {
                    keySet[MAP[nx][ny] - 'a'] = true;
                    while (!Door[MAP[nx][ny] - 'a'].empty()) {
                        Q.push(Door[MAP[nx][ny] - 'a'].front());
                        Door[MAP[nx][ny] - 'a'].pop();
                    }
                }
            } else {
                Q.push({nx, ny});
                if (MAP[nx][ny] == '$') {
                    res++;
                }
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> T;
    while (T--) {
        cin >> h >> w;
        for (int i = 1; i <= h; i++) {
            string str;
            cin >> str;
            for (int j = 1; j <= w; j++) {
                MAP[i][j] = str[j-1];
            }
        }
        string str;
        cin >> str;
        if (str[0] != '0') {
            for (int i = 0; i < str.length(); i++) {
                keySet[str[i] - 'a'] = true;
            }
        }

        searchMap(0, 0);
        cout << res << "\n";
        init();
    }

    return 0;
}