깊이우선탐색(DFS) 알고리즘 with 파이썬
DFS는 깊이 우선 탐색이라고 부른다.
그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
스택자료구조나 재귀함수를 이용하며 구체적인 동작은 다음과 같다.
- 탐색 시작 노드를 스택에 삽입하고 방문처리를 한다
- 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리를 한다. 방문하지 않은 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
- 2번의 과정을 수행할 수 없을 때까지 반복한다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | def dfs(graph, v, visited): # 현재 노드를 방문처리 visited[v] = True print(v, end = ' ') # 현재 노드와 연결된 다른 노드를 재귀적으로 방문 for i in graph[v]: if not visited[i]: dfs(graph, i, visited) graph = [ [], [2, 3, 8], [1, 7], [1, 4, 5], [3, 5], [3, 4], [7], [2, 6, 8], [1, 7] ] visited = [False] * 9 dfs(graph, 1, visited) |
그냥 기본기니까 암기해두자!!
