백준 9328. 열쇠

tose33 2022. 8. 16. 15:51

9328번: 열쇠

상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가

www.acmicpc.net

푸는 중에 로직을 여러번 바꿔 시간이 지체되고 오래 끌수록 집중력이 떨어져 엄청 오래걸렸다..

일단 내가 푼 방식은 다음과 같다.

1. 맵을 입력받는다

2. 최초부터 보유중인 키들을 입력 받는다.

보유 중인 키들에 대한 문들은 모두 통과 가능하므로 맵에서 지워버린다. 키도 지워 버린다.

3. 모든 입구를 시작점으로 bfs 탐색한다.

여기서 입구란 태두리 부분 이면서, 비어있는 공간 이거나 (.), 키이거나 (소문자), 문서 ($) 인 경우다.

4. (3)번을 새로운 키나 문서를 발견하지 못할때까지 반복한다.