[백준] 1194번 달이 차오른다, 가자

1194 달이 차오른다 가자

문제

---

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

빈 곳 : 언제나 이동할 수 있다. ('.‘로 표시됨

벽 : 절대 이동할 수 없다. (‘#’

열쇠 : 언제나 이동할 수 있다. 이 곳에 처음 들어가면 열쇠를 집는다. (a - f)

문 : 대응하는 열쇠가 있을 때만 이동할 수 있다. (A - F)

민식이의 현재 위치 : 빈 곳이고, 민식이가 현재 서 있는 곳이다. (숫자 0)

출구 : 달이 차오르기 때문에, 민식이가 가야하는 곳이다. 이 곳에 오면 미로를 탈출한다. (숫자 1)

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

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

입력

---

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

출력

---

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

---

풀이)

bfs와 bit-masking을 이용해서 푼 문제이다. 복잡하다.

key를 하나만 가질 수 있는게 아니고 여러 개를 동시에 가질 수 있다.

key를 가진 상태를 키가 6개니깐 6 비트로 표현했다.

0번째 비트는 a, 1번째 비트는 b, 2번째 비트는 c 이런식으로.

f e d c b a

5 4 3 2 1 0

---

비트 상태      integer

0 0 0 0 0 0 -> 0, 아무 키도 가지고 있지 않은 상태

0 0 0 0 0 1 -> 1, a키만 가지고 있는 상태

0 0 0 0 1 0 -> 2, b키만 가지고 있는 상태

0 0 0 0 1 1 -> 3, a키와 b키를 가지고 있는 상태

.

.

0 1 0 0 0 0 -> 16, e키만 가지고 있는 상태

.

.

1 0 0 1 0 1 -> 35, a키와 c키 f키를 가지고 있는 상태

.

.

1 1 1 1 1 1 -> 63, 모든 키를 가지고 있는 상태

---

그리고 키를 가진 상태에 따라 맵을 이동하는데 중복된 곳은 피하기 위해

bool visited[50][50][64] 3차원 배열로 방문한 곳을 표시하기로 했다.

bool visited[i][j][k] == true 는 i 행 j 열 번째 칸을 key상태가 k일 때 방문했었다 라는 뜻이다.

주의

키를 나타내는 a, b, c, d, e, f는 ASCII로 97~102이다.

문을 나타내는 A, B, C, D, E, F는 ASCII로 65~102이다.

코드)

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
int n, m;
char map[50][50];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
pair<int, int> minsik;
//key를 000000 6비트로 표시, 비트가 1일경우 해당하는 열쇠를 가진다는뜻
//0 0 0 0 0 0
//f e d c b a
bool visited[50][50][64]; 
 
int bfs() {
    queue<pair<pair<int, int>,int>>qu;//좌표와 열쇠종류
    qu.push({ { minsik.first, minsik.second } ,0});
    visited[minsik.first][minsik.second][0] = true; //일단 아무 열쇠를 가지지 않은 경우
    int cnt = 0;
    while (!qu.empty())
    {
        int size = qu.size();
        while (size--)
        {
            int y = qu.front().first.first;
            int x = qu.front().first.second;
            int key = qu.front().second;
            qu.pop();
 
            for (int i = 0; i < 4; i++) {
                int ny = y + dy[i];
                int nx = x + dx[i];
                if (ny >= 0 && ny < n && nx >= 0 && nx < m) {
                    //이미 접근했었거나 벽이면 pass
                    if (visited[ny][nx][key] || map[ny][nx] == '#')continue;
 
                    if (map[ny][nx] == '1') return cnt + 1;//만일 미로 탈출할 수 있다면
 
                    if (map[ny][nx] == '.' || map[ny][nx] == '0') {//빈곳일 경우
                        visited[ny][nx][key] = true;
                        qu.push({ {ny,nx} ,key });
                    }
                    else {//열쇠거나 문일경우
                        int temp = (int)map[ny][nx];
                        //a~f = 97~102, A~F = 65~70
                        if (temp > 90) {//열쇠
                            temp -= 97;
                            if (key & (1 << temp)) { //temp번째 열쇠를 이미 가지고 있었다면
                                visited[ny][nx][key] = true;
                                qu.push({ {ny,nx} ,key });
                            }
                            else {
                                //열쇠 추가
                                visited[ny][nx][key | (1 << temp)] = true; //temp번째 비트도 1로 바꾼다.
                                qu.push({ {ny,nx} ,key | (1 << temp) });
                            }
                        }
                        else {//문
                            temp -= 65;
                            if (key & (1 << temp)) {//temp번째 문에 해당하는 열쇠를 가지고 있었다면
                                visited[ny][nx][key] = true;
                                qu.push({ {ny,nx} ,key });
                            }
                            //안가지고 있다면 이동 불가
                        }
                    }
                }
            }
        }
        cnt++;
    }
    return -1;
}
 
int main() {
    scanf("%d %d", &n, &m);
    getchar();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%c", &map[i][j]);
            if (map[i][j] == '0') minsik = { i,j };
        }
        getchar();
    }
    printf("%d", bfs());
 
    return 0;
}

결과)