알고리즘 문제/etc
2. 깊이 우선 탐색 (DFS, depth first search)
요네리
2021. 8. 16. 16:04
완전 탐색
그래프를 탐색하는 방법중에 brute-force 라는 방법이 있습니다.
Brute(무식한) + Force(힘) 라는 의미로 극단적으로 말하자면 무식하게 모든 자료를 찾아본다는 방법입니다.
그 중에 그래프의 전체 노드를 탐색하는 것을 완전 탐색이라고 합니다.
완전 탐색의 종류로는 대표적으로 깊이 우선 탐색(dfs), 너비 우선 탐색(bfs) 가 있습니다.
깊이 우선 탐색 (Depth First Search)
깊이 우선 탐색(이하 DFS)는 루트 노드에서 탐색을 시작하여 리프 노드의 끝까지 탐색을 하는 방법입니다.
그 다음 리프 노드에서 끝이 나면 바로 윗 레벨의 다른 분기의 다른 리프 노드의 끝까지 탐색을 이어나갑니다.
즉, 가장 깊은 노드 = 리프 노드 = 가장 최대 레벨의 노드 를 우선적으로 탐색한다는 의미에서 '깊이 우선 탐색'이라고 합니다.
탐색 순서
1) 루트 노드를 가장 먼저 방문 표시
2) 방문한 노드에서 연결된 이웃 노드 중, 방문하지 않은 노드 중, 가장 첫번째 순서 혹은 가장 작은 번호의 노드를 방문
3) 리프 노드까지 반복 수행
4) 리프노드 바로 직전에 방문한 노드로 돌아가서, 방문하지 않은 다른 이웃 노드를 방문
5) 더 이상한 방문할 이웃 노드가 없으면, 상위의 부모 노드로 다시 이동하여 방문하지 않은 이웃 노드를 찾는다.
6) 더이상 방문할 노드가 없을 때까지 반복한다.
결과적으로 탐색 순서는 1->2->4->7->8->5->3->6->9 입니다.
소스 코드 구현
DFS 를 구현하는 방법에는 2가지 방법이 있습니다.
- 재귀호출 이용
- 스택 이용
# 인접 행렬을 이용한 그래프 구현
graph = [
[0, 1, 1, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 1, 1, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 1, 0, 0, 0],
[0, 1, 0, 0, 0, 0, 1, 1, 0],
[0, 1, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 0, 0, 1],
[0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 1, 0, 0, 0]
]
# 방문을 기록할 visit 배열 = 노드의 갯수
visit = [False] * 9
# 깊이 우선 탐색 함수
def dfs(node):
visit[node] = True
for i in range(9):
if graph[node][i] == 1 and visit[i]:
dfs(i)
return
#함수 수행
dfs(0)
코딩테스트를 위해 풀어보면 좋은 문제