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

문제

 

---

풀이

 

그냥 평범한 bfs로 풀 수 있을 것 같은데 생각을 하나 해야한다.

예제 입력 1을 보면 알 수 있듯이 이미 방문한 정점이지만 f 열쇠를 획득한 이후엔 다시 방문할 수 있다.

열쇠 보유 '상태'가 달라졌기 때문이다.

 

https://myunji.tistory.com/289

[백준] 2206번 : 벽 부수고 이동하기

이 문제랑 비슷한 개념인데, 참고로 저 문제 이제 완벽하게 이해해서 관련 문제도 2차원 배열 내에서 다 해결했다. 뿌듯

 

아무튼 저 문제에서의 상태는 '벽을 부순 횟수'이다. 이 문제에선 그게 '보유한 열쇠의 종류'로 바뀌었을 뿐이다.

지금 어떤 열쇠를 갖고있는지 알기 위해 비트마스킹을 쓸 것이다.

 

열쇠는 a-f로 총 6개다. 6개의 비트로 표현할 수 있다는 것이다.

000000 : 보유한 열쇠 없음

000010 : b 열쇠 보유

010001 : a, e 열쇠 보유

 

이러한 가능한 상태 조합은 총 2^6 = 64개이다.

N, M의 최대 크기가 50이라고 했으니 50*50*64 크기의 3차원 배열은 충분히 감당할 수 있다.

 

사실 이걸 벽 부수기 시리즈처럼 2차원 배열에 압축할 수 있을까 싶었는데, 안될 것 같다.

---

소스코드

 

#include <iostream>
#include <vector>
#include <queue>
#include <string>

using namespace std;
typedef pair<int, int> pp;

struct info { //행, 열, 거리, 보유 열쇠 상태
    int r, c, d, s;
};

int N, M;
vector<vector<char>> board;
vector<vector<vector<bool>>> visited;
pp dir[4] = {{-1, 0},  //상
             {1,  0},  //하
             {0,  -1}, //좌
             {0,  1}}; //우

int bfs(info start) {
    queue<info> q;
    visited[start.r][start.c][start.s] = true; //시작점 초기화
    q.push(start);
    while (!q.empty()) {
        int row = q.front().r;
        int col = q.front().c;
        int dist = q.front().d;
        int status = q.front().s;
        q.pop();

        if (board[row][col] == '1') //출구
            return dist;
        for (int i = 0; i < 4; i++) {
            int nr = row + dir[i].first;
            int nc = col + dir[i].second;
            int ns = status;
            if ((nr < 0) || (nr >= N) || (nc < 0) || (nc >= M) || (board[nr][nc] == '#')) //범위를 벗어나거나 벽
                continue;
            if (isupper(board[nr][nc]) && !(status & (1 << (board[nr][nc] - 'A')))) //문인데 열쇠가 없음
                continue;
            if (islower(board[nr][nc])) //열쇠라면 획득처리
                ns |= (1 << (board[nr][nc] - 'a'));
            if (!visited[nr][nc][ns]) { //미방문 정점
                visited[nr][nc][ns] = true; //방문 처리
                q.push({nr, nc, dist + 1, ns});
            }
        }
    }
    return -1; //출구 찾지 못함
}

int main() {
    string input;
    info start{};

    cin >> N >> M;
    board.assign(N, vector<char>(M));
    visited.assign(N, vector<vector<bool>>(M, vector<bool>(1 << 6))); //열쇠는 a-f 6개
    for (int i = 0; i < N; i++) {
        cin >> input;
        for (int j = 0; j < M; j++) {
            board[i][j] = input[j];
            if (board[i][j] == '0') //시작점
                start = {i, j, 0, 0};
        }
    }
    cout << bfs(start);
}

전체 소스코드다.

 

struct info { //행, 열, 거리, 보유 열쇠 상태
    int r, c, d, s;
};

각 정점의 상태를 나타낼 구조체다.

 

int main() {
    string input;
    info start{};

    cin >> N >> M;
    board.assign(N, vector<char>(M));
    visited.assign(N, vector<vector<bool>>(M, vector<bool>(1 << 6))); //열쇠는 a-f 6개
    for (int i = 0; i < N; i++) {
        cin >> input;
        for (int j = 0; j < M; j++) {
            board[i][j] = input[j];
            if (board[i][j] == '0') //시작점
                start = {i, j, 0, 0};
        }
    }
    cout << bfs(start);
}

입력받으면서 시작점을 체크해둔다.

시작점에선 당연히 갖고있는 열쇠가 없을테니 status가 0이다.

 

int bfs(info start) {
    queue<info> q;
    visited[start.r][start.c][start.s] = true; //시작점 초기화
    q.push(start);
    while (!q.empty()) {
        int row = q.front().r;
        int col = q.front().c;
        int dist = q.front().d;
        int status = q.front().s;
        q.pop();

        if (board[row][col] == '1') //출구
            return dist;
        for (int i = 0; i < 4; i++) {
            int nr = row + dir[i].first;
            int nc = col + dir[i].second;
            int ns = status;
            if ((nr < 0) || (nr >= N) || (nc < 0) || (nc >= M) || (board[nr][nc] == '#')) //범위를 벗어나거나 벽
                continue;
            if (isupper(board[nr][nc]) && !(status & (1 << (board[nr][nc] - 'A')))) //문인데 열쇠가 없음
                continue;
            if (islower(board[nr][nc])) //열쇠라면 획득처리
                ns |= (1 << (board[nr][nc] - 'a'));
            if (!visited[nr][nc][ns]) { //미방문 정점
                visited[nr][nc][ns] = true; //방문 처리
                q.push({nr, nc, dist + 1, ns});
            }
        }
    }
    return -1; //출구 찾지 못함
}

bfs 함수다.

 

    queue<info> q;
    visited[start.r][start.c][start.s] = true; //시작점 초기화
    q.push(start);

먼저 시작점을 초기화 하고

 

        int row = q.front().r;
        int col = q.front().c;
        int dist = q.front().d;
        int status = q.front().s;

while문을 돌면서 정점의 정보를 빼온다.

 

        if (board[row][col] == '1') //출구
            return dist;

만약 출구를 찾았다면 바로 리턴하고

 

        for (int i = 0; i < 4; i++) {
            int nr = row + dir[i].first;
            int nc = col + dir[i].second;
            int ns = status;
            if ((nr < 0) || (nr >= N) || (nc < 0) || (nc >= M) || (board[nr][nc] == '#')) //범위를 벗어나거나 벽
                continue;
            if (isupper(board[nr][nc]) && !(status & (1 << (board[nr][nc] - 'A')))) //문인데 열쇠가 없음
                continue;
            if (islower(board[nr][nc])) //열쇠라면 획득처리
                ns |= (1 << (board[nr][nc] - 'a'));
            if (!visited[nr][nc][ns]) { //미방문 정점
                visited[nr][nc][ns] = true; //방문 처리
                q.push({nr, nc, dist + 1, ns});
            }
        }

상하좌우로 이동해본다.

 

            if ((nr < 0) || (nr >= N) || (nc < 0) || (nc >= M) || (board[nr][nc] == '#')) //범위를 벗어나거나 벽
                continue;

범위를 벗어나거나, 벽이라면 이동할 수 없다.

 

            if (isupper(board[nr][nc]) && !(status & (1 << (board[nr][nc] - 'A')))) //문인데 열쇠가 없음
                continue;

만약 대문자, 즉 문이라면 해당 문에 맞는 열쇠가 있는지 확인한다.

문이 A일 때 상태가 000001, 100001, 000011, 001001...등등 아무튼 A에 해당하는 첫번째 비트가 1이여야 문이 열린다.

 

            if (islower(board[nr][nc])) //열쇠라면 획득처리
                ns |= (1 << (board[nr][nc] - 'a'));

만약 소문자, 즉 열쇠라면 status를 갱신해서 열쇠 획득처리 한다.

 

            if (!visited[nr][nc][ns]) { //미방문 정점
                visited[nr][nc][ns] = true; //방문 처리
                q.push({nr, nc, dist + 1, ns});
            }

이제 새로운 좌표, 새로운 상태에 대해 방문하지 않았다는걸 확인하면 방문처리 하고 큐에 넣는다.

 

    return -1; //출구 찾지 못함

큐가 빌때까지 출구를 찾지 못했다면 -1을 리턴한다.

 

    cout << bfs(start);

메인에서 그 결과를 출력하면 된다.