백준) 1194 달이 차오른다, 가자.

1194 달이 차오른다, 가자.

문제

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

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

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

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

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

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

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

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

입력

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

출력

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

예제 입력 

1 7
f0.F..1

예제 출력 

7

1. 접근

행렬을 순회하면서 최소 이동 횟수를 찾아야 하기 때문에 BFS를 채용.

2. 세부사항

열쇠를 습득했는지 여부에 따라 이동방식이 바뀌기 때문에 매번 방문시 열쇠 보유 상태를 갱신하고 기억해야한다.

따라서 삼차원 행렬을 BFS로 순회하면서 탐색한다. X, Y 축이 미로이고, Z축이 열쇠 보유 상태인 셈.

시작점이 주어지고 지도에서 1을 찾으면 종료되므로,

최악의 경우 모든 지점을 방문하는 N*M*(가능한 열쇠보유 상태의 경우)에 비례.

3. 코드

#include <stdio.h>
#include <queue>
#include <algorithm>
using namespace std;
 
char map[50][51];
int visit[50][50][1 << 7]; //6자리 2진수를 만들기 위해 7번 시프트
int d[4][2] = { {-1, 0},{1, 0},{0, -1},{0, 1} };
int n, m, stx, sty;
 
int bfs() {
    visit[stx][sty][0] = 1;
    queue<pair<pair<int, int>, int>> q;
    q.push({ {stx, sty}, 0 });
 
    while (!q.empty()) {
        int qs = q.size();
        while (qs--) {
            int x = q.front().first.first;
            int y = q.front().first.second;
            int k = q.front().second;
            q.pop();
 
            if (map[x][y] == '1')
                return visit[x][y][k] - 1;
 
            for (int i = 0; i < 4; ++i) {
                int xx = x + d[i][0];
                int yy = y + d[i][1];
 
                if (xx < 0 || yy < 0 || xx >= n || yy >= m || map[xx][yy] == '#' || visit[xx][yy][k] != 0)
                    continue;
                if ('a' <= map[xx][yy] && map[xx][yy] <= 'f') {
                    int kk = k | (1 << (map[xx][yy] - 'a')); // OR연산으로 열쇠보유상태를 갱신
                    if (visit[xx][yy][kk] == 0) {
                        visit[xx][yy][k] = visit[x][y][k] + 1;
                        visit[xx][yy][kk] = visit[x][y][k] + 1;
                        q.push({ {xx, yy}, kk });
                    }
                }
                else if ('A' <= map[xx][yy] && map[xx][yy] <= 'F') {
                    int kk = k & (1 << (map[xx][yy] - 'A')); // AND연산으로 해당 열쇠를 보유 중인지 확인
                    if (kk != 0) {
                        visit[xx][yy][k] = visit[x][y][k] + 1;
                        q.push({ {xx, yy}, k });
                    }
                }
                else if (visit[xx][yy][k] == 0) {
                    visit[xx][yy][k] = visit[x][y][k] + 1;
                    q.push({ {xx, yy}, k });
                }
            }
        }
    }
    return -1;
}
 
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; ++i) {
        scanf("%s", map[i]);
        for (int j = 0; j < m; ++j) {
            if (map[i][j] == '0') {
                stx = i;
                sty = j;
            }
        }
    }
    printf("%d", bfs());
 
    return 0;
}

4. 후기

열쇠 보유 상태를 어떤 형식으로 저장해야 하는지 한참 헤맸다.

비트마스킹 기법을 새롭게 알게 되었으니 기억하도록 하자.

처음 제출 했을 당시엔 열쇠 상태 갱신에만 신경쓰다보니 메모리 초과가 떴다.

열쇠 레벨로 올라가고 (Z축) 큐에 남겨진 기존 레벨들의 탐색을 처리해주지 않아서 였다.