[2020 카카오 기출] 동굴 탐험

 

programmers.co.kr/learn/courses/30/lessons/67260

---

jacob님의 풀이(velog.io/@jacob0122/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%8F%99%EA%B5%B4-%ED%83%90%ED%97%98)를 참고하여 해결했습니다.

 

BFS로 풀이를 했고, 특정 노드간에 생기는 선-후 관계를 before[], nxt[]로 표현했습니다.

 

또한 임의의 노드 A를 방문할 수 있었지만, 노드A와 선-후 관계에서 '선'에 위치하는 노드를 아직 방문하지 않은 경우

노드A를 waitingList라는 set에 넣어서 '선'에 위치하는 노드를 방문할 때 노드 A도 방문할 수 있도록 해줍니다.

 

이런식으로 BFS를 특수하게 돌리면 order관계(== 선후 관계)를 만족하면서 방문 여부를 판단할 수 있습니다.

 

자세한 내용은 주석을 참고하시면 됩니다.

---

코드: github.com/cottory/algorithm/blob/master/PROGRAMMERS/PG67260.cc