파이썬 코딩테스트 스터디 8주차 #3 - 그래프 탐색 : 너비 우선 탐색

 

너비 우선 탐색

 

 

1.  큐가 비어있는지 확인. 비었다면 방문할 수 있는 모든 노드를 방문했다는 의미
2. 비어있지 않으면, 큐에서 노드 팝
3. 팝한 노드와 인접한 모드 노드 확인, 아직 방문 안한 노드를 큐에 푸시

 

 

큐를 활용한 너비 우선 탐색

 

코딩 테스트 합격자 되기 : 파이썬 편 - 387p

\

코딩 테스트 합격자 되기 : 파이썬 편 - 388p

코딩 테스트 합격자 되기 : 파이썬 편 - 389p

 

 

너비우선 탐색은 가중치가 없는 그래프에서 최단 경로 보장.

 

즉, 최단 경로 찾는 경우는 너비 우선 탐색

아니면 깊이 우선 탐색.

 

너비우선 탐색 예제 : 미로 찾기, 최단 경로, 네트워크 분석

 

 

 

깊이 우선 탐색은 스택에서 팝할 때 방문처리

너비 우선 탐색은 큐에 푸시할 때 방문처리

 

 

♬ 자료 출처 - 책

코딩 테스트 합격자 되기 - 파이썬 편

 

 

 

이 포스팅의 모든 내용은 해당 책의 내용을 바탕으로 하고 있습니다. 

감사합니다.