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

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

 

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

 

문제

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

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

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

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

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

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

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

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

 

입력

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

 

출력

첫째 줄에 민식이가 미로를 탈출하는데 드는 이동 횟수의 최솟값을 출력한다. 만약 민식이가 미로를 탈출 할 수 없으면, -1을 출력한다.첫째 줄에는 치즈가 모두 녹아서 없어지는 데 걸리는 시간을 출 력하고, 둘째 줄에는 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 출력한다.

 

예제 입력

1 7
f0.F..1

4 7
1F....f
A.....a
.#...##
....0..

 

예제 출력

7

11

 

해결방법

개인적으로 정~~~말 어려웠던 문제이다

접근법 자체가 떠오르지 않아 다른 블로그를 참고하여 문제를 해결했다

 

알고리즘을 설계할 때 가장 어려웠던 부분은 아래와 같다

1. 중복 방문을 어떻게 처리 ????
2. 현재 가지고 있는 열쇠를 어떻게 나타낼까 ???

 

⭐️ 1번 : 중복 방문을 어떻게 처리 ??? ⭐

2차원 배열은 한번 방문하면 visited 을 true 로 두고 중복 방문을 막아야 할까??

 

다른 BFS 탐색에서는 최단 거리를 구하기 위해 이미 지나온 노드를 방문 체크하여 중복 방문을 방지했다

하지만 이 문제는 열쇠를 구하러 갔다가 다시 그 길을 방문 할 수 있었다

 

따라서 visited 배열을 2차원이 아닌 3차원으로 나타낼 필요가 있다

어? 이런 접근은 어디서 해본적 있는데....???

14442번 벽 부수고 이동하기2

 

……..!!!!!

각 방문시 상태를 두는 방법이었다

벽 부수고 이동하기의 예를 들어보자

• 만약 벽을 하나 부쉈다면 visited[n][m][0] 을 방문 처리

• 만약 벽을 두개 부쉈다면 visited[n][m][1] 을 방문 처리

 

이처럼 다른 상태별로 방문을 처리한다면 중복 방문을 처리할 수 있다!!!

 

 

⭐️ 2번 : 현재 가지고 있는 열쇠를 어떻게 나타낼까 ??? ⭐

열쇠의 보유 여부를 이용해 어떻게 다른 상태로 나타낼까??

 

이 문제를 풀며 비트 마스킹 기법을 새로 공부했다

비트 마스킹이란??

 

열쇠는 a, b, c, d, e, f 총 6개의 열쇠가 있다

따라서 이를 2진수로 나타낸다면 0 0 0 0 0 0 ~ 1 1 1 1 1 1 로 나타낼 수 있다!!

최대의 경우인 모든 열쇠를 가지고 있는 경우는 63으로 배열이므로 배열로 충분히 나타낼 수 있다

 

따라서 아래와 같이 3차원 배열을 사용해 방문을 체크해줬다

bool visited[MAX][MAX][64];

 

 

최단거리 문제이면서 중복 탐색을 허용하는 문제를 많이 안풀어봤지만

이번 기회에 비트 마스킹과 더불어 뭔가 새로 배운 느낌이다...!!

꼭 다른 문제도 풀어봐야겠다 🤞

 

 

 

소스코드

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <cstring>
#include <set>
#include <queue>
#include <vector>
#include <algorithm>
#define MAX 51
#define INF 987654321
using namespace std;

struct node {
    int x,y,cnt,key;
    
    node() { }
    node(int _x,int _y,int _cnt,int _key) : x(_x),y(_y),cnt(_cnt),key(_key) { }
};

int n,m;
char map[MAX][MAX];
bool visited[MAX][MAX][64];

int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};

node s;

void bfs(){
    queue<node> q;
    q.push(s);
    visited[s.x][s.y][s.key] = true;
    
    while(!q.empty()){
        int x = q.front().x;
        int y = q.front().y;
        int cnt = q.front().cnt;
        int key = q.front().key;
        q.pop();
        
        // 출구를 만난 경우 (여러개 일 수도 있음)
        if(map[x][y] == '1'){
            cout << cnt << "\n";
            return;
        }
        
        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx<0 || ny<0 || nx>=n || ny>=m) continue;
            if(map[nx][ny] == '#') continue;
            
            // 열쇠를 만난 경우
            if(map[nx][ny]>='a' && map[nx][ny]<='f'){
                int add_key = key | (1 << (map[nx][ny]-'a'));
                
                if(visited[nx][ny][add_key]) continue;
                
                q.push(node(nx,ny,cnt+1,add_key));
                visited[nx][ny][add_key] = true;
            }
            // 문을 만난 경우
            else if(map[nx][ny]>='A' && map[nx][ny]<='F'){
                int chk_key = key & (1 << (map[nx][ny]-'A'));
                
                if(chk_key==0 || visited[nx][ny][key]) continue;
                
                q.push(node(nx,ny,cnt+1,key));
                visited[nx][ny][key] = true;
            }
            // 나머지 경우
            else{
                if(visited[nx][ny][key]) continue;
                
                q.push(node(nx,ny,cnt+1,key));
                visited[nx][ny][key] = true;
            }
        }
    }
    cout << -1 << "\n";
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n >> m;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin >> map[i][j];
            
            if(map[i][j] == '0'){
                s.x = i;
                s.y = j;
            }
        }
    }
    
    memset(visited, false, sizeof(visited));
    bfs();
    
    return 0;
}