A. 문제설명
9328번: 열쇠
상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가
www.acmicpc.net
문제에 대한 자세한 설명은 링크 참조
1. 상근이는 빌딩에 침입해 문서를 훔치려고 함
2. 빌딩에는 문이 있고, 문을 열려면 해당 알파벳의 열쇠가 필요함
3. 열쇠는 주어지기도 하고, 주워서 얻을 수도 있음
4. 빌딩의 각 공간은 아래와 같은 규칙을 가짐
'.'는 빈 공간을 나타낸다.
'*'는 벽을 나타내며, 상근이는 벽을 통과할 수 없다.
'$'는 상근이가 훔쳐야하는 문서이다.
알파벳 대문자는 문을 나타낸다.
알파벳 소문자는 열쇠를 나타내며, 그 문자의 대문자인 모든 문을 열 수 있다.5. 상근이가 훔칠 수 있는 문서의 수를 구하라
B. 접근법
BFS
문제에서 주요한 요점은 문제 이름인 '열쇠'이다. 상근이는 빌딩의 가장자리에서 접근이 가능하므로 가장자리를 돌며 방문되지 않은 지역을 시작으로 BFS 탐사하여 매 회마다 열쇠를 찾으면서 keys 배열에 업데이트한다. 더이상 새로운 열쇠가 획득되지 않으면, 더 이상 새로운 문서를 찾을 수 있는 탐사가 이루어질 수 없는 것이므로 그 턴을 마지막으로 종료한다.
C. 풀이
1. 매 회마다 열쇠를 찾으면서 keys 배열에 업데이트
2. 열쇠 - 'a', 문 - 'A'로 확인
3. 가장자리를 돌며 방문되지 않은 지역을 시작으로 BFS
4. 3에서 더이상 새로운 열쇠가 획득되지 않으면, 그 턴을 마지막으로 종료
D. 내 코드
