[Programmers] 동굴 탐험

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/67260

프로그래머스

 

BFS를 응용한 알고리즘 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. 트리를 구성한 뒤 각 방에 대해 `방문하기 전에 반드시 방문해야 하는 방`을 저장하는 배열 pre를 정의합니다.

 

2. BFS를 통해 0번 방에서 시작해서 방문합니다.

• 만약 시작점인 0번 방 이전에 방문해야 하는 방이 있다면 탐험 자체가 불가능하므로 바로 종료
• 인접한 방 (next)에 대해, 만약 pre[next] (next 이전에 방문해야 하는 방)가 아직 방문되지 않았다면, 해당 방 (next)은 현재 바로 방문할 수 없으므로 대기 리스트(waiting)에 기록
• 현재 방문한 방이 다른 방의 선행 조건일 경우 대기 목록에서 해당 방을 찾아 큐에 넣어 바로 방문할 수 있도록 처리
• 선행 조건이 충족되었거나 조건이 없을 경우 해당 방을 방문 처리

 

3. BFS 탐색 종료 후 모든 방이 방문되었는지 확인

 

 

개발환경: Programmers IDE  

 

지적, 조언, 질문 환영합니다! 질문 남겨주세요~