반응형
깊이 우선 탐색
하나를 깊이 파고 든다
a와 인접한 다른 노드 차례로 순회한다
a와 인접한 노드 b를 방문했다면, a와 인접한 다른 노드를 방문하기 위해서는 b와 인접한 노드를 전부 방문한 뒤
a와 인접한 b를 제외한 다른 노드를 방문할 수 있다
- 스택 : 경로 정보의 추적을 기록
DFS 구현
딕셔너리와 스택을 활용
인접한 노드를 저장하는 adjDict는 연결리스트로 노드의 데이터를 key로 갖는다
방문 정보를 확인하는 visitedInfo는 노드의 데이터를 key로 value에는 방문했을때 1을 저장
python
반응형
'프로그래밍 > 자료구조, 알고리즘' 카테고리의 다른 글
| [알고리즘]너비우선탐색(BFS) (0) | 2022.08.11 |
|---|---|
| [알고리즘]정렬 (0) | 2022.08.03 |
| [자료구조]이진탐색트리 (0) | 2022.07.29 |
| [자료구조]그래프 (0) | 2022.07.25 |
| [자료구조]힙(Heap), 우선순위 큐 (0) | 2022.07.22 |