DFS 알고리즘

DFS (Depth-First Search )

• 깊이 우선 탐색
• 깊게 들어가다가 더 이상 들어갈 곳이 없다면 끝
• 그래프의 깊은 부분을 우선적으로 탐색하는 알고리즘
• 스택 & 재귀함수를 이용

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2. 방문하지 않은 노드가 하나라도 있으면 스택에 넣고 방문 처리를 한다.
3. 2번의 과정을 수행할수 없을때 까지 반복한다.

# DFS 함수 정의
def dfs(graph, v, visited):
    # 현재 노드를 방문 처리
    visited[v] = True
    print(v, end=' ')
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
  [],
  [2, 3, 8],
  [1, 7],
  [1, 4, 5],
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1, 7]
]

# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9

# 정의된 DFS 함수 호출
dfs(graph, 1, visited)

참조 : 동빈나 유튜브