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

문제 링크 : www.acmicpc.net/problem/1194

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

문제를 봤을 때 BFS로 풀어야 하는 문제이구나! 하는 느낌은 바로 받을 수 있지만,

막상 문제를 해결하려고 하면 생각이 복잡해지는 문제이다.

 

출구를 향해 일단 가다가 잠긴 문을 만나면 목적지를 열쇠로 바꿔가면서 가는 방법을 제일 처음 생각해 볼 수 있다.

이 방법은 각 출구마다의 최단경로 path를 기억해 놓고, 통과해야 하는 문이 어떤 문들인지를 파악한 후에

가장 가까운 열쇠부터 획득하는 순서로 알고리즘이 진행되어야 하지만, 상당히 복잡하다.

또한, 출구의 개수에 제한이 없기 때문에 출구가 많을수록 느린 방식이다.

 

이 문제를 깔끔하게 푸는 핵심 아이디어는 열쇠를 획득한 순간, 획득하기 전의 경로와 별개로 진행하게 된다는 점이다.

쉽게 말하자면, 어떤 열쇠를 획득하고 나면 획득한 상태를 저장한 상태에서 새로 탐색을 한다는 것이다.

 

획득한 열쇠의 상태를 Bitmask 형태로 나타내고, 각 State마다 visit 배열을 두어 열쇠 획득 전후의 탐색을 구분한다.

위 그림과 같이 열쇠를 얻으면 해당 State에 해당하는 visit으로 올라간다고 생각하면 된다.

이 방법을 따르면 한 번의 BFS를 통해 모든 출구에 대한 최단경로를 찾을 수 있다.

 

[코드]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
 
using namespace std;
typedef tuple<int, int, int> tup;
 
int r, c;
//문 또는 열쇠는 board상에서 아스키 값으로 저장
int board[51][51], visit[1 << 6][51][51]; 
pair<int, int> startpoint;
int dir_r[4] = { -1, 0, 1, 0 };
int dir_c[4] = { 0, 1, 0, -1 };
 
int bfs() {
    //bfs로 start - end 의 최단거리를 구한다.
    queue<tup> que;
    que.push({ 0, startpoint.first, startpoint.second });
    visit[0][startpoint.first][startpoint.second] = true;
 
    while (!que.empty()) {
        tup cur = que.front();
        que.pop();
        
        int key = get<0>(cur);
        int row = get<1>(cur);
        int col = get<2>(cur);
 
        //end에 도착한 경우
        if (board[row][col] == -2) return visit[key][row][col];
 
        //문을 만난 경우
        if (board[row][col] >= 'A' && board[row][col] <= 'F') {
            //맞는 열쇠가 없다면 통과 불가
            bool open = key & (1 << (board[row][col] - 'A'));
            if (!open) continue;
        }
 
        //열쇠를 만난 경우
        int newkey = key;
        if (board[row][col] >= 'a' && board[row][col] <= 'f') {
            newkey |= (1 << (board[row][col] - 'a'));
        }
        
        for (int i = 0; i < 4; i++) {
            int newr = row + dir_r[i];
            int newc = col + dir_c[i];
 
            //범위 체크
            if (newr < 1 || newr > r || newc < 1 || newc > c) continue;
            //벽 체크
            if (board[newr][newc] == -1) continue;
            //방문여부 체크
            if (visit[newkey][newr][newc]) continue;
            visit[newkey][newr][newc] = true;
 
            que.push({ newkey, newr, newc });
            visit[newkey][newr][newc] = visit[key][row][col] + 1;
        }
    }
    //경로가 없는 경우
    return -1;
}
 
void init() {
    scanf("%d %d", &r, &c);
    for (int i = 1; i <= r; i++) {
        string input;
        cin >> input;
        for (int j = 0; j < c; j++) {
            if (input[j] == '.') { board[i][j + 1] = 0; continue; }
            if (input[j] == '#') { board[i][j + 1] = -1; continue; }
            if (input[j] == '1') { board[i][j + 1] = -2; continue; }
            if (input[j] == '0') { startpoint.first = i; startpoint.second = j + 1; continue; }
            board[i][j + 1] = input[j];
        }
    }
}
 
int main() {
    init();
    int result = bfs();
    if (result != -1) result -= 1;
    printf("%d\n", result);
 
    return 0;
}