1194. 달이 차오른다, 가자.

본문에서 약간의 새벽감성이 느껴진다. ㅋㅋ

1194번: 달이 차오른다, 가자.

---

미로를 돌아다니며 열쇠를 얻어서 출구로 나가야 하는 문제이다.

 

당연히 이런 류의 문제는 BFS를 적용하면 된다. 그런데 조금 불편한 조건이 하나 있다. 

미로에는 문이 있을 수 있는데, 대응하는 열쇠가 있어야 문을 지나갈 수 있다.

벽뿐만 아니라 문도 신경쓰면서 bfs를 해야 한다. 이러한 조건 때문에, 일반적으로 bfs할 때 쓰는 2차원 visit 배열로는 정답을 구할 수 없다. 

 

예제 입력 1을 보자.

이 입력에서 최단 경로는 열쇠 f를 획득한 후 오른쪽 맨 끝의 출구로 가는 경로이다. 이동하는 과정에서 출발 지점을 다시 방문하게 된다. 2차원 visit 배열로는 이것을 처리할 수 없다.

 

민식이는 왜 이미 방문했던 곳을 지나갈 수 있었는가? 이 질문에 대한 답을 구하면 문제를 해결할 수 있다. 열심히 생각해 보고, 그래도 잘 모르겠다면 아래 글을 읽자.

민식이가 열쇠를 얻었기 때문이다. 즉, 열쇠를 얻기 전의 민식이와 얻은 후의 민식이는 구별되어야 한다.

 

열쇠 상태를 저장하는 가장 좋은 방법은 비트마스크를 사용하는 것이다. 열쇠가 6종류뿐이기 때문에 비트마스크를 인덱스로 사용하여 3차원 visit 배열에 접근할 수 있다. boolean 6개짜리 배열을 사용해도 되지만, 메모리와 속도 면에서 비트마스크가 더 효율적이다.

 

처음 시작할 때는 아무 열쇠도 갖고 있지 않다. 이제 탐색을 시작해 보자.

---

지난 문제도 그렇고 이 문제도.. 스포일러 주의