[백준 1194번] 달이 차오른다, 가자. (C++)

 

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

1194번: 달이 차오른다, 가자.

---

달이 차오른다, 가자 문제는 벽 부수고 이동하기, 말이 되고픈 원숭이와 유사하며,

BFS와 백트래킹을 이용하여 해결할 수 있습니다.

 

문제에서 열쇠는 'a', 'b', 'c', 'd', 'e', 'f만 등장합니다.

따라서 비트마스킹을 사용한다면, 현재 갖고 있는 열쇠의 현황을 6비트로 표현할 수 있습니다.

BitMasking

---

예를 들어 111111은 6개의 키를 모두 얻은 상태를 의미하며, 000000은 어떠한 키도 얻지 못한 상태를 의미합니다.

101100인 상태에서 키 'b'를 얻은 경우, 101100와 000010을 비트 or 연산을 수행하면, 101110을 얻을 수 있습니다.

즉, 키 'b'를 현재 갖고 있다고 표시할 수 있습니다.

  101100
| 000010
----------
  101110

또한, 101100와 000010을 비트 and 연산을 수행하면, 현재 키 'b'를 갖고 있는지를 확인할 수 있습니다.

  101100
& 000010
----------
  000000 -> false -> 키 'b'를 갖지 않음
  

  101100
& 000100
----------
  000100 -> true -> 키 'c'를 갖고 있음

 

💡 Solution

---

아래는 알고리즘의 기본 틀입니다. 

1. BFS를 수행하며, 미로를 탈출하는데 드는 최소 이동 횟수를 계산
   (단, (nx, ny)는 인접한 좌표, Keys는 현재 갖고 있는 열쇠를 표현하는 이진수)
   
   • (nx, ny)가 문인 경우,
     1. keys에 비트 and 연산을 수행하여, 해당 문을 열 수 있는 열쇠를 갖고 있는지 확인
     2. keys 상태로, (nx, ny) 위치로 이동한 적이 없거나, 현재 위치에서 방문하는 것이 더 최단 거리인 경우
        백트래킹으로 문을 열고 이동
   • (nx, ny)가 열쇠인 경우
     1. keys에 비트 or 연산을 수행하여, 해당 열쇠를 추가 
     2. added 상태로 아직 방문한 적이 없거나, 현재 위치에서 방문하는 것이 더 최단 거리인 경우, 키를 습득하고 백트래킹으로 이동
        (단, added는 keys에 해당 열쇠를 추가한 이진수)
   • (nx, ny)가 빈 공간인 경우
     1. keys 상태로 방문하지 않은 경우, 현재 상태에서 방문하는 것이 더 최단 거리인 경우 이동
2. 도착 가능한 탈출구 중에서 가장 최단 거리를 출력

 

아래는 전체 코드입니다.

// Created by 길민호 on 2022/08/10.

#include <bits/stdc++.h>
using namespace std;

#define x first
#define y second

char board[100][100];
int vis[100][100][65];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
int n, m;

// st는 시작 지점
// distInit는 앞서 이동한 거리
// keys는 현재 갖고 있는 키를 나타내는 이진수
void bfs(pair<int, int> st, int distInit, int keys){
    queue<pair<int, int>> q;
    q.push(st);
    vis[st.x][st.y][keys] = distInit + 1;   // 방문 표시 배열에 시작점을 (앞서 이동한 거리 + 1)로 설정

    while(!q.empty()){
        pair<int, int> cur = q.front(); q.pop();

        for(int dir = 0; dir < 4; dir++){
            int nx = cur.x + dx[dir];
            int ny = cur.y + dy[dir];

            if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;    // 미로를 벗어나는 경우
            char c = board[nx][ny]; // 다음에 이동할 곳의 문자
            if(c == '#') continue; // 벽인 경우

            if((c >= 'A' && c <= 'Z')){ // 문인 경우
                int key = c - 'A';  // 해당 문을 여는 키를 나타내는 비트의 위치
                if(keys & (1 << key)){ // 비트마스킹으로 열쇠를 가지고 있는지 확인
                    // 현재 keys 상태로 아직 방문한 적이 없거나
                    // 이전에 keys 상태에서 (nx, ny)로 이동한 것 보다, 현재 위치에서 방문하는 것이 더 최단거리인 경우
                    // 문을 열고 이동해봄
                    if(vis[nx][ny][keys] == 0 ||
                       vis[nx][ny][keys] > vis[cur.x][cur.y][keys] + 1){
                        board[nx][ny] = '.';    // 문을 빈 공간으로 만듦
                        // (nx, ny)가 시작점, keys는 그대로, distInit은 현재까지 이동한 거리
                        bfs({nx, ny}, vis[cur.x][cur.y][keys], keys);
                        board[nx][ny] = c;  // 문을 원래 상태로 복구
                    }
                }
            }else if(c >= 'a' && c <= 'z'){   // 열쇠인 경우
                int key = c - 'a';  // 해당 열쇠를 갖고 있는지 나타내는 bit의 위치
                int addKey = keys | (1 << key); // or 연산을 통해 keys에 현재 위치에 놓인 키를 추가
                // addKey 상태로 아직 방문한 적이 없거나
                // 이전에 addKey 상태에서 (nx, ny)로 이동한 것 보다, 현재 위치에서 방문하는 것이 더 최단거리인 경우
                // 키를 습득하고 이동
                if(vis[nx][ny][addKey] == 0 ||
                   vis[nx][ny][addKey] > vis[cur.x][cur.y][keys] + 1){
                    // (nx, ny)가 시작점, keys는 현재 위치에 놓인 키를 추가한 이진수, distInit은 현재까지 이동한 거리
                    bfs({nx, ny}, vis[cur.x][cur.y][keys], addKey);
                }
            }else{  // 빈 칸인 경우
                // keys 상태로 방문하지 않은 경우,
                // 현재 상태에서 (nx, ny) 위치로 이동하는 것이 더 최단거리인 경우
                // (nx, ny) 위치로 이동
                if(vis[nx][ny][keys] == 0
                   || vis[nx][ny][keys] > vis[cur.x][cur.y][keys] + 1){
                    q.push({nx, ny});
                    vis[nx][ny][keys] = vis[cur.x][cur.y][keys] + 1;
                }
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    pair<int, int> st;  // 민식이의 위치

    for(int i = 0; i < n; i++){ // 미로 입력 받음
        for(int j = 0; j < m; j++){
            cin >> board[i][j];
            if(board[i][j] == '0') st = {i, j}; // 민식이의 위치 저장
        }
    }

    // BFS를 수행하며, 미로를 탈출하는데 드는 최소 이동횟수를 계산
    bfs(st, 0, 0); // 아직 이동하지 않았으므로, distInit은 0으로 설정

    int ans = INT_MAX;
    for(int i = 0; i < n; i++){ // 도착 가능한 탈출구 중에서 가장 최단 거리를 출력
        for(int j = 0; j < m; j++){
            if(board[i][j] == '1'){
                for(int k = 0; k < 64; k++){
                    if(vis[i][j][k] != 0){
                        ans = min(ans, vis[i][j][k] - 1);
                    }
                }
            }
        }
    }

    if(ans == INT_MAX) ans = -1;
    cout << ans << "\n";
}

 

아래는 문제 해결에 사용된 테스트케이스입니다.

5 5
....1
#1##A
.1.#a
....0
.1.#.
-> 3