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

 

 

 

 

 

깊이 우선 탐색

시작 노드부터 탐색을 시작해, 간선을 따라 최대 깊이 노드까지 이동하며 차례대로 방문.

1. 최대 깊이 노드까지 방문 후
2. 이전 방문한 노드를 거슬러 올라가 연결된 노드에서 방문하지 않은 노드부터 다시 최대 깊이까지 차례대로 방문!

 

스택 활용 방법

1. 시작 노드 정한다.
2. 스택에 시작노드 푸시
3. 스택이 비었는 지 확인 → 비었다면, 모든 노드 방문했음 → 탐색 종료
4. 스택에서 노드 팝한다. (팝한 노드는 최근에 푸시한 노드)
5. 팝한 노드의 방문 여부 확인 →  방문 처리
6. 방문한 노드와 인접한 노드 확인  →  비 방문 노드 푸시 

깊이 우선 탐색의 핵심  

: 가장 깊은 노드까지 방문 후, 더 이상 방문할 노드 없으면, 최근 방문한 노드로 돌아온 다음,

해당 노드에서 방문할 노드가 있는지 확인.

 

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

스택을 활용한 깊이 우선 탐색

선입후출의 특성을 가진 스택으로 가장 최근에 방문 노드 확인 가능. 

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

 

 

Push → Pop →방문여부 확인 및 처리 → 인접 노드 Push 

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

 

 

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

 

재귀 함수를 활용한 깊이 우선 탐색

dfs(N) : N번 노드를 방문 처리하고, N번 노드와 인접한  노드중 아직 방문하지 않은 노드를 탐색

 

 

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

 

 

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

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

 

 

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

 

 

 

깊이 우선 탐색에서는 Stack활용시 

Pop할 때, 방문처리를 한다.

 

최단 경로를 찾는 문제를 제외하고는 '깊이 우선 탐색'을 활용한다.

 

 

 

♬ 자료 출처 - 책

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

 

 

 

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

감사합니다.