[BOJ] 9328 열쇠 (C/C++)

9328번: 열쇠

문제

상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 필요하다. 상근이는 일부 열쇠를 이미 가지고 있고, 일부 열쇠는 빌딩의 바닥에 놓여져 있다. 상근이는 상하좌우로만 이동할 수 있다.

상근이가 훔칠 수 있는 문서의 최대 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 수는 100개를 넘지 않는다.

각 테스트 케이스의 첫째 줄에는 지도의 높이와 너비 h와 w (2 ≤ h, w ≤ 100)가 주어진다. 다음 h개 줄에는 빌딩을 나타내는 w개의 문자가 주어지며, 각 문자는 다음 중 하나이다.

• '.'는 빈 공간을 나타낸다.
• '*'는 벽을 나타내며, 상근이는 벽을 통과할 수 없다.
• '$'는 상근이가 훔쳐야하는 문서이다.
• 알파벳 대문자는 문을 나타낸다.
• 알파벳 소문자는 열쇠를 나타내며, 그 문자의 대문자인 모든 문을 열 수 있다.

마지막 줄에는 상근이가 이미 가지고 있는 열쇠가 공백없이 주어진다. 만약, 열쇠를 하나도 가지고 있지 않는 경우에는 "0"이 주어진다.

상근이는 처음에는 빌딩의 밖에 있으며, 빌딩 가장자리의 벽이 아닌 곳을 통해 빌딩 안팎을 드나들 수 있다. 각각의 문에 대해서, 그 문을 열 수 있는 열쇠의 개수는 0개, 1개, 또는 그 이상이고, 각각의 열쇠에 대해서, 그 열쇠로 열 수 있는 문의 개수도 0개, 1개, 또는 그 이상이다. 열쇠는 여러 번 사용할 수 있다.

---

입력을 보고 있으면 어지러운 문제지만 그리 어렵지는 않았다. 단순한 BFS 문제에 조금의 아이디어만 더하면 풀 수 있었다.

 

첫 번째 아이디어는 BFS의 시작점이 따로 정해지지 않았다는 점을 해결하기 위해 필요하다. 벽에 구멍이 뚫린 부분이 BFS의 시작점이 되어야겠지만 그런 부분이 한 개 일지 여러 개 일지는 알 수 없다. 따라서 입력으로 주어지는 지도 바깥에 빈 공간을 둘러준다. 그러고 나서 시작 지점을 그중 하나로 하면 따로 예외를 처리해주지 않아도 상근이가 알아서 벽이 빈 곳을 찾아 지도로 들어가게 된다. 빈 공간의 어떤 곳이든 상관없지만 가장 단순한 (0, 0)을 시작 지점으로 골랐다. 

 

두 번째 아이디어는 열쇠가 없어서 문을 지났지만 이후에 열쇠를 얻게 되는 경우를 처리하는 데에 필요하다. 첫 번째 입력만 보더라도 처음엔 c랑 z 열쇠만 주어지지만 이후에 p 열쇠를 얻고 그 열쇠로 x, y 열쇠를 얻어서 문서를 얻을 수 있다. 이걸 해결하기 위해서 각 문의 큐를 따로 만들고 열쇠 없이 지나가는 경우엔 큐에 좌표를 넣어둔다. 나중에 열쇠를 얻게 되면 그 큐에 들어있는 좌표들을 BFS 큐로 옮겨준다. 그럼 상근이가 열쇠를 얻고 나서 문 앞으로 순간 이동하는 효과를 볼 수 있다. 열쇠를 한 번만 사용할 수 있다고 하면 또 골치 아프겠지만, 이 문제에선 열쇠는 횟수 제한이 없어서 그냥 쉽게 했다.

 

처음에는 약간 헤맸지만 아이디어만 생각하고 나면 구현은 그렇게 어렵지 않았다. 중간에 실수로 오타를 낸 채로 제출을 했는데도 맞았습니다가 나왔다. 뭘까...? ㅋㅋㅋㅋ

 

 

후기)

이제 solved.ac의 클래스5 문제도 거의 다 풀어간다. 이제 3문제밖에 안 남았다.

다른 분들이 난이도 의견 남기신걸 보면 다른 방법도 많은 것 같다.