DFS (깊이우선탐색)

DFS는 깊이 우선 검색을 나타냅니다. 트리 또는 그래프 데이터 구조를 순회하거나 검색하는 데 사용되는 알고리즘입니다. 알고리즘은 루트라고 하는 특정 노드에서 시작하여 역추적하기 전에 각 분기를 따라 가능한 멀리 탐색합니다.

DFS는 재귀 또는 명시적 스택을 사용하여 구현할 수 있습니다. 재귀를 사용할 때 알고리즘은 방문할 노드를 기억하기 위해 호출 스택에 의존합니다. 또는 명시적 스택을 사용하여 노드를 추적할 수 있습니다.

DFS 작동방식

1. 루트 노드에서 시작합니다.
2. 깊이 우선 방식으로 현재 노드의 인접 노드를 탐색합니다. 즉, 하나의 인접 노드를 방문하고 역추적하기 전에 인접 노드를 재귀적으로 탐색합니다.
3. 방문하지 않은 노드가 없을 때까지 2단계를 반복합니다.
4. 방문하지 않은 노드가 남아 있는 경우 그 중 하나를 새로운 현재 노드로 선택하고 2, 3단계를 반복합니다.
5. 모든 노드를 방문했으면 알고리즘이 완료됩니다.

ex)

0 > 1 > 2 > 3

2 > 4

1 > 5 > 6

0 > 7

0 > 7 > 8

7 > 9 > 10

9 > 11

9 > 12

DFS 예제

adj = [[0] * 13 for _ in range(13)]
adj[0][1] = adj[0][7] = 1
adj[1][2] = adj[1][5] = 1

# for row in adj:
#     print(row)


def dfs(now):
    for nxt in range(13):
        if adj[now][nxt]:
            dfs(nxt)


dfs(0)