깊이 우선 탐색(DFS : Depth First Search) 이론과 파이썬 구현

깊이 우선 탐색(DFS : Depth First Search)

 

깊이 우선 탐색(DFS : Depth First Search)은 시작점으로부터 갈 수 있는 점 중 한 곳을 가서 그 곳에서 또 방문할 수 있는 점을 가서 방문할 수 있는 점이 없을 때까지 깊게 갔다 나오는 탐색 방법입니다.

 

깊이 우선 탐색은 크게 2가지 문제에서 자주 사용됩니다.

1. 그래프를 모두 탐색하는 문제

2. 특정 조합을 뽑는 문제

 

깊이 우선 탐색의 방법은
1. 하나의 점을 방문하고
2. 하나의 점과 연결 되어 있는 곳을 모두 방문하고 나옵니다.

 

깊이 우선 탐색에서는 재귀 함수를 이용합니다.

 

위와 같은 그래프가 있다고 가정하고 깊이 우선 탐색을 실시해보겠습니다.

 

시작점은 1로 생각하고 모든 그래프를 탐색하려고 합니다.

점을 방문할때는 더 작은 순서로 방문하도록 하겠습니다.

 

깊이 우선 탐색(DFS) 과정 1

 

방문했는지 확인하기 위한 배열에 모든 값을 0으로 초기화합니다.

 

기존 그래프에서 1을 처음 방문합니다.

방문 완료를 배열의 1 자리의 값을 1로 바꾸는 것을 통해 알려줍니다.

 

1과 연결된 점은 2와 3이 있는데 작은 것을 먼저 방문하기로 했으니 2를 방문합니다.

배열의 2 자리의 값을 1로 바꿔줍니다.

 

 

깊이 우선 탐색(DFS) 과정 2

2과 연결된 점은 4와 5가 있는데 작은 것을 먼저 방문하기로 했으니 4를 방문합니다.

배열의 4 자리의 값을 1로 바꿔줍니다.

 

4와 연결된 점은 2인데 2는 이미 방문을 했고 더이상 방문할 점이 없습니다.

4번에서 직전에 방문한 점인 2로 되돌아옵니다.

그 후 2에서 방문하지 않은 5를 방문합니다.

배열의 5 자리의 값을 1로 바꿔줍니다.

 

5와 연결된 점은 2인데 2는 이미 방문을 했습니다.

2와 연결된 점은 1, 4, 5가 있는데 모두 방문을 했습니다.

그럼 1로 돌아갑니다.

 

1과 연결된 점은 2와 3인데 방문하지 않은 3으로 가서 방문을 합니다.

배열 3 자리의 값을 1로 바꿔줍니다.

 

 

깊이 우선 탐색(DFS) 과정 3

 

3과 연결된 점 중 방문하지 않은 6을 방문합니다.

 

6과 연결된 점 중 방문하지 않은 점이 없으므로 3으로 돌아갑니다.

3에서도 방문하지 않은 점이 없기 때문에 1로 돌아갑니다.

1번에서도 방문할 점이 없습니다.

 

그럼 모든 점들의 방문이 끝나 탐색이 종료됩니다.

 

위의 그래프에서 깊이 우선 탐색의 방문 순서는 1 → 2 → 4 → 5 → 3→ 6 입니다.

 

재귀 함수를 이용한 깊이 우선 탐색의 파이썬 코드입니다.

n = 6 #정점의 수 : 6 (1, 2, 3, 4, 5, 6)
v = 1 #시작점
b = [[1, 2], [1, 3], [2, 4], [2, 5], [3, 6]]

a = [[] for i in range(n+1)]

for i in range(len(b)):
    x, y = b[i]
    a[x].append(y)
    a[y].append(x)
    
for i in a: # 작은 수부터의 방문을 위해 정렬
    i.sort()

ch = [0] * (n+1)

def dfs(node):
    ch[node] = 1
    print(node, end=' ')

    for i in a[node]:
        if ch[i] != 1:
            dfs(i)

dfs(v)

# 최종 출력>>1 2 4 5 3 6