[BAEKJOON] 1194. 달이 차오른다, 가자

Posted on January 15, 2021

문제 :

지금 민식이가 계획한 여행은 달이 맨 처음 뜨기 시작할 때 부터, 준비했던 여행길이다. 하지만, 매번 달이 차오를 때마다 민식이는 어쩔 수 없는 현실의 벽 앞에서 다짐을 포기하고 말았다.

민식이는 매번 자신의 다짐을 말하려고 노력했지만, 말을 하면 아무도 못 알아들을 것만 같아서, 지레 겁먹고 벙어리가 되어버렸다. 결국 민식이는 모두 잠든 새벽 네시 반쯤 홀로 일어나, 창 밖에 떠있는 달을 보았다.

하루밖에 남지 않았다. 달은 내일이면 다 차오른다. 이번이 마지막기회다. 이걸 놓치면 영영 못간다.

영식이는 민식이가 오늘도 여태것처럼 그냥 잠 들어버려서 못 갈지도 모른다고 생각했다. 하지만 그러기엔 민식이의 눈에는 저기 뜬 달이 너무나 떨렸다.

민식이는 지금 미로 속에 있다. 미로는 직사각형 모양이고, 여행길을 떠나기 위해 미로를 탈출하려고 한다. 미로는 다음과 같이 구성되어져있다.

빈 곳 : 언제나 이동할 수 있다. (‘.‘로 표시됨)
벽 : 절대 이동할 수 없다. (‘#’)
열쇠 : 언제나 이동할 수 있다. 이 곳에 처음 들어가면 열쇠를 집는다. (a - f)
문 : 대응하는 열쇠가 있을 때만 이동할 수 있다. (A - F)
민식이의 현재 위치 : 빈 곳이고, 민식이가 현재 서 있는 곳이다. (숫자 0)
출구 : 달이 차오르기 때문에, 민식이가 가야하는 곳이다. 이 곳에 오면 미로를 탈출한다. (숫자 1)

달이 차오르는 기회를 놓치지 않기 위해서, 미로를 탈출하려고 한다. 한 번의 움직임은 현재 위치에서 수평이나 수직으로 한 칸 이동하는 것이다.

민식이가 미로를 탈출하는데 걸리는 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.

입력 :

첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, 영식이가 열쇠를 숨겨놓는 다면 문에 대응하는 열쇠가 없을 수도 있다. 0은 한 개, 1은 적어도 한 개 있다. 그리고, 열쇠는 여러 번 사용할 수 있다.

출력 :

첫째 줄에 민식이가 미로를 탈출하는데 드는 이동 횟수의 최솟값을 출력한다. 만약 민식이가 미로를 탈출 할 수 없으면, -1을 출력한다.

풀이 :

BFS 알고리즘에서 방문 여부를 체크하는 방식을 효과적으로 구현해야 풀 수 있는 문제였다.

좀 더 명확히 설명하자면 현재 위치를 무작정 방문한 적 있다고 판단해서는 안되고 현재 내가 획득한 키의 종류와 갯수를 고려해 방문 여부를 체크해주어야 한다.

만약 키의 갯수만 고려한다면 가령 a, b 키를 가지고 있는 경우와 b, c 키를 가지고 있는 경우를 동일하게 인식하기 때문에 문제를 해결할 수 없다.

따라서 난 비트 연산자를 활용하여 a~f 총 6개의 키를 6자리 2진수로 생각하고 구현에 들어갔다.

따라서 visit 배열은 2^65050 3차원 배열로 구현했다.

그 외에는 각 칸의 글자를 확인하고 탐색해 들어가면 답을 여느 문제와 동일하게 구할 수 있다.

코드 :

코드 보기/접기

#include <iostream>
#include <queue>
#include <algorithm>

#define INF 987654321

using namespace std;
typedef struct Qnode {
    int x, y, dist, keycnt;
} Qnode;

bool visit[64][50][50];
char map[50][50];
int w, h, di[4] = {0, 1, 0, -1}, dj[4] = {1, 0, -1, 0};

int bfs(int x, int y) {
    queue<Qnode> q;
    int ansdist = INF;
    q.push(Qnode{x, y, 0, 0});
    visit[0][x][y] = true;

    while (!q.empty()) {
        int curx = q.front().x, cury = q.front().y, curd = q.front().dist, curcnt = q.front().keycnt;
        q.pop();
        for (int k = 0; k < 4; k++) {
            int cmpx = curx + di[k], cmpy = cury + dj[k];
            if (0 <= cmpx && cmpx < h && 0 <= cmpy && cmpy < w && map[cmpx][cmpy] != '#') {
                if (map[cmpx][cmpy] == '1') ansdist = min(ansdist, curd + 1);
                else if (map[cmpx][cmpy] == '.' && !visit[curcnt][cmpx][cmpy]) {
                    q.push(Qnode{cmpx, cmpy, curd + 1, curcnt});
                    visit[curcnt][cmpx][cmpy] = true;
                } else if ('a' <= map[cmpx][cmpy] && map[cmpx][cmpy] <= 'f') {
                    int cmpcnt = curcnt | (1 << (map[cmpx][cmpy] - 'a'));
                    if (!visit[cmpcnt][cmpx][cmpy]) {
                        q.push(Qnode{cmpx, cmpy, curd + 1, cmpcnt});
                        visit[cmpcnt][cmpx][cmpy] = true;
                    }
                } else if ('A' <= map[cmpx][cmpy] && map[cmpx][cmpy] <= 'F' &&
                           (curcnt & (1 << (map[cmpx][cmpy] - 'A'))) && !visit[curcnt][cmpx][cmpy]) {
                    q.push(Qnode{cmpx, cmpy, curd + 1, curcnt});
                    visit[curcnt][cmpx][cmpy] = true;
                }
            }
        }
    }
    return ((ansdist == INF) ? -1 : ansdist);
}

int main() {
    int stx, sty;
    cin >> h >> w;
    for (int i = 0; i < h; i++)
        for (int j = 0; j < w; j++) {
            cin >> map[i][j];
            if (map[i][j] == '0') {
                stx = i;
                sty = j;
                map[i][j] = '.';
            }
        }
    cout << bfs(stx, sty) << '\n';
    return 0;
}

Algorithm

algorithm baekjoon C++