백준 9328 - 열쇠

썸네일 사진은 제 열쇠입니다.

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

9328번: 열쇠

multi-source BFS로 해결했다.

 

0. 전처리

입력받은 지도를 순회하며, 가장자리에 통로가 있을 경우 BFS의 시작 위치로 추가한다. 이때 통로가 꼭 '.'만 가능한 것은 아님에 유의하자. 열쇠나 문서도 이동할 때는 통로와 같은 취급을 받는다.

 

그리고 현재 어떤 열쇠를 보유 중인지 확인하기 위해 bool key[26] 배열을 사용했다. 마지막 줄에 입력받은 열쇠, 지도의 가장자리에 있는 열쇠는 전처리에서 확인할 수 있다.

 

마지막으로 내 풀이에서는 key 배열처럼 알파벳마다 문의 위치를 저장하는 pair<int, int> door[26] 배열을 사용했다. 이 배열의 쓰임새는 아래에서 더 설명한다.

 

1.

일반적인 BFS를 수행한다. 즉 큐에서 매번 맨 앞의 위치를 pop하여 상하좌우 중 이동 가능하고 방문하지 않은 위치를 큐의 끝에 추가한다. 이때, 이동 가능한 4가지 경우(통로, 열쇠, 문, 문서)에 대해 처리 방식이 조금씩 다르다.

 

- 통로, 문서

일반적인 방식으로 방문 표시 후 큐의 끝에 추가한다. 문서일 경우 count를 1 증가시킨다.

 

- 문

해당 문에 맞는 열쇠를 보유하고 있을 경우 통로처럼 처리한다.

만약 열쇠가 없을 경우 방문 표시만 한 뒤 큐에 추가하지는 않는다. 여기서의 방문 표시는 '출발지점에서 이 문에 도달할 수 있음' 을 뜻한다.

 

- 열쇠

key 배열을 갱신한 뒤, 해당 키로 열 수 있는 모든 문의 위치(door 배열 이용)를 새로운 큐에 추가한다.

char temp = graph[nxt_row][nxt_col];
if (temp >= 'a' && temp <= 'z') {
    key[temp - 'a'] = 1;

    for (auto p : door[temp - 'a'])
        nxt_q.push(p);
}

 

2.

BFS를 수행하다보면 어느새 큐가 빌 경우, 즉 더 이상 이동할 수 없는 상황에 다다를 것이다.

이제 1에서 문과 열쇠를 처리했던 결과를 이용해 새로운 위치에서 BFS를 시작해야한다.

새로운 위치란 어디일까? 잘 생각해보면 '이번 BFS를 통해 열쇠를 얻어 지나갈 수 있게 된 문' 일 것이다. 이 위치를 어떻게 찾을 수 있을까?

 

우리는 BFS 중 새 열쇠를 발견했을 때 nxt_q에 해당 키로 열 수 있는 모든 문의 위치를 저장했다. 따라서 현재의 BFS가 끝나면 nxt_q에는 이번 BFS에서 얻은 열쇠로 지나갈 수 있는 문의 위치가 저장돼있다. 그러나 무턱대고 nxt_q의 모든 위치를 새 출발 지점으로 설정하면 안된다. 아래의 예시를 보자.

 

1
5 5
**.**
**bB*
***$*
*B$**
*****
0

열쇠 b로 열 수 있는 문 B의 위치는 (1,3)과 (3,1) 두 개지만, (3,1)에 있는 문은 실제로는 도달할 수 없으므로 새 출발 지점으로 설정하면 안 된다. 따라서 우리는 nxt_q에 저장된 위치 중 BFS로 도달 가능한 위치, 즉 visited[i][j]가 true인 위치만 사용할 것이다. 1에서 지나가지도 못 하는 문의 방문 여부를 갱신한 이유는 이 때문이다.

//현재 BFS가 종료되면
if (cur_q.empty()) {

    //이번에 얻은 열쇠로 지나갈 수 있는 문 중
    while (!nxt_q.empty()) {
        int nxt_row = nxt_q.front().first;
        int nxt_col = nxt_q.front().second;

        //BFS로 방문했던 (도달 가능한) 문만 다음 BFS의 시작 위치로 추가
        if(visited[nxt_row][nxt_col])
            cur_q.push(nxt_q.front());
        nxt_q.pop();
    }
}

3. 유의사항

전처리 과정에서 '가장자리의 문'을 유의해야 한다.

 

내부에 위치한 문은 열쇠 유무를 확인한 후 큐에 추가하므로 상관 없지만, 가장자리의 문은 전처리 구현 방식에 따라 열쇠가 없어도 큐의 시작 위치에 추가될 수 있다. 그렇다고 무작정 문을 시작 위치에서 배제해서도 안 된다. 아래의 두 예시를 보고 고민해보자.

input
1
3 3
*A*
*$*
***
0

answer
0

input
1
3 3
*A*
*$*
***
a

answer
1

전처리 과정에서 가장자리에 문이 있을 때 열쇠 유무를 확인하거나, BFS문에 아래와 같은 코드를 추가해 시작 위치가 '열쇠 없는 문'이 되는 경우를 방지하자.

//temp := graph[cur_row][cur_col]

//시작 위치가 문인데 열쇠가 없을 경우
if (temp >= 'A' && temp <= 'Z' && !key[temp - 'A']) continue;

 

<이 문제에서 내가 고전했던 점>

가장자리 처리, '다음 시작 위치' 구현, 특이 케이스 (열쇠 없이 문에서 시작하는 경우) 파악