[BOJ]9328번: 열쇠

 

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

---

jaimemin님 풀이를 참고하여 해결하였습니다. (https://jaimemin.tistory.com/692)

 

문제 풀이에 필요한 아이디어는 아래와 같습니다.

1. 모든 칸에서 입장이 가능하다는 조건을 위해 주어진 그래프 테두리에 빈 칸을 추가해서 모든 칸 방문하게 하기

2. 열쇠를 새로 얻으면 그 지점부터 bfs를 다시 시작합니다.

3. 열쇠나 문서를 얻었으면 재방문을 막기 위해 빈 칸으로 바꿔버립니다.

 

위와 같은 기법을 통해 bfs를 돌리면 문제를 해결할 수 있습니다.

---

코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ9328.cc