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

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

---

비트마스킹 BFS 그래프탐색

[문제해석]

 

  '0' 지점에서 '1' 지점까지 탐색을 진행하는데 'a','b','c','d','e','f' 는 열쇠고 'A','B','C','D','E','F'는 각각 소문자 열쇠로 열 수 있는 문이다. 문을 열려면 열쇠가 있는 지점을 먼저 방문해서 열쇠를 가지고 방문해야된다.

 

[알고리즘풀이]

 

 전형적인 비트마스킹을 활용한 그래프 탐색 문제로 열쇠가 6 종류 밖에 없는 점에 집중해 비트마스킹으로 현재 어떤 열쇠들을 가지고 있는지 표현해주면 된다. 

 visited[X][Y][curS] := (X, Y) 지점에 curS 열쇠 상태로 방문했을 때 최소 이동 횟수 라고 정의하면 문제를 쉽게 해결할 수 있다.

 

 1) 다음에 이동할 지점이 '.' 거나 '1' 이면 현재 이동 횟수 + 1 이 해당 지점에 현재 상태로 방문한 가장 작은 값이라면 이동을 진행한다.

 

 2) 다음에 이동할 지점이 열쇠가 있고 현재 이동 횟수 + 1 이 해당 지점에 현재 상태로 방문한 가장 작은 값이라면 이동을 진행한다. 그 후, 현재 상태에 해당 지점의 열쇠를 갱신해준다.

 | (OR) 연산을 이용하면 쉽게 갱신할 수 있다.

 ( curS | (1 << key) ) 

 

 3) 다음에 이동할 지점이 문이 있고 현재 이동 횟수 + 1 이 해당 지점에 현재 상태로 방문한 가장 작은 값이고, 현재 열쇠 상태가 해당 문을 열 수 있다면 이동을 진행한다.

 & (AND) 연산을 이용하면 현재 열쇠 상태로 문을 열 수 있는지 쉽게 확인할 수 있다.

 ( curS & (1 << door) )

 

[ 주의사항 ]

 

 열쇠가 총 6종류 이므로 비트마스킹을 (1 << 7) 로 진행해야되는데, (1 << 6) 으로 셋팅해서 개고생을 했다....! 조심, 또 조심!

 

[ 정답코드 ]

#include<iostream>
#include<queue>
using namespace std;
 
struct position {
    int x, y, s, l;
};
 
const int INF = 9999999;
int r, c;
int visited[50][50][1 << 7];
int dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, -1, 0, 1 };
char map[50][51];
 
bool checkIndex(int x, int y) {
    return (0 <= x && x < r && 0 <= y && y < c);
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> r >> c;
    for (int i = 0; i < r; i++)
        cin >> map[i];
    for (int i = 0; i < r; i++) // 초기화
        for (int j = 0; j < c; j++)
            for (int k = 0; k < (1 << 7); k++)
                visited[i][j][k] = INF;
 
    queue<position> q;
    for (int i = 0; i < r; i++) // 시작점 찾기
        for (int j = 0; j < c; j++)
            if (map[i][j] == '0') {
                visited[i][j][0] = 0;
                q.push({ i, j, 0, 0 });
                map[i][j] = '.';
            }
    while (!q.empty()) { // 탐색진행
        int curX = q.front().x, curY = q.front().y, curS = q.front().s, curL = q.front().l;
        q.pop();
        if (map[curX][curY] == '1') continue;
 
        for (int i = 0; i < 4; i++) {
            int nextX = curX + dx[i], nextY = curY + dy[i];
            if (!checkIndex(nextX, nextY)) continue;
            if (map[nextX][nextY] == '#') continue;
            if ((map[nextX][nextY] == '.' || map[nextX][nextY] == '1') && curL + 1 < visited[nextX][nextY][curS]) { // 그냥 갈 수 있는 길
                visited[nextX][nextY][curS] = curL + 1;
                q.push({ nextX, nextY, curS, curL + 1 });
            }
            else if ('a' <= map[nextX][nextY] && map[nextX][nextY] <= 'f' && curL + 1 < visited[nextX][nextY][curS]) {
                int key = (map[nextX][nextY] - 'a') + 1;
                visited[nextX][nextY][curS] = curL + 1;
                q.push({ nextX, nextY, curS | (1 << key), curL + 1 });
            }
            else if ('A' <= map[nextX][nextY] && map[nextX][nextY] <= 'F' && curL + 1 < visited[nextX][nextY][curS]) {
                int door = (map[nextX][nextY] - 'A') + 1;
                if (curS & (1 << door)) {
                    visited[nextX][nextY][curS] = curL + 1;
                    q.push({ nextX, nextY, curS, curL + 1 });
                }
            }
        }
    }
    
    int ans = INF; // '1' 인 지점에 방문한 값 중 최소값 찾기
    for (int i = 0; i < r; i++)
        for (int j = 0; j < c; j++)
            if (map[i][j] == '1')
                for (int k = 0; k < (1 << 7); k++)
                    ans = min(ans, visited[i][j][k]);
    if (ans == INF) ans = -1;
    cout << ans << '\n';
}

---