[알고리즘] DFS : 깊이 우선 탐색

DFS & BFS?

• 자료의 검색, 트리나 그래프를 탐색하는 방법. 한 노드를 시작으로 인접한 다른 노드를 재귀적으로 탐색해가고 끝까지 탐색하면 다시 위로 와서 다음을 탐색하여 검색한다.
• 한 노드를 시작으로 인접한 모든 정점들을 우선 방문하는 방법. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 넓이 우선 검색을 적용한다.

왜 DFS & BFS 를 배울까요?

정렬된 데이터를 이분 탐색하는 것처럼 아주 효율적인 방법이 있는 반면에,
모든 경우의 수를 전부 탐색해야 하는 경우도 있습니다.

DFS 와 BFS 는 그 탐색하는 순서에서 차이가 있습니다.
DFS 는 끝까지 파고드는 것이고,
BFS 는 갈라진 모든 경우의 수를 탐색해보고 오는 것이 차이점입니다.

DFS

• 끝까지 파고드는 것 👉 그래프의 최대 깊이 만큼의 공간을 요구
• 공간을 적게 씀
• 최단 경로 탐색 어려움

BFS

• 최단 경로 찾기 쉬움 -> 모든 분기되는 수를 다 탐색
• 모든 분기되는 수를 다 저장 -> 공간을 많이 씀
• 모든 걸 탐색 -> 시간이 더 오래걸릴 수 있습니다.

DFS 개념

• Depth First Search
• 노드를 방문하고 깊이 우선으로 인접한 노드를 방문한다.
• 또 그 노드를 방문해서 깊이 우선으로 인접한 노드를 방문한다.
• 만약 끝에 도달했다면 리턴한다.

DFS의 방문 방식

👉 DFS(node) = node + DFS(node와 인접하지만 방문하지 않은 다른 node) 반복

• 방문 조건을 어떻게 알 수 있을까?
  👉 visited 배열에 방문 노드 기록

시작 노드를 정하고 여기에서 출발한다.

1. 현재 방문한 노드를 visited 에 추가한다.
2. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드에 방문한다.
3. 2부터 반복한다.

# 위의 그래프를 인접 리스트 방식으로 표현
graph = {
    1: [2, 5, 9],
    2: [1, 3],
    3: [2, 4],
    4: [3],
    5: [1, 6, 8],
    6: [5, 7],
    7: [6],
    8: [5],
    9: [1, 10],
    10: [9]
}

단계가 너무 많으니 1에서 5까지 탐색하는 경우만 예시로 보기로 하자.

• visited = [] 방문한 걸 저장하기 위한 배열
• 탐색 시작 노드 = 1

👇 탐색 과정 👇

1. 현재 노드 : 1 / 현재 방문한 노드인 1을 visited 에 추가
   → visited -> [1]
2. 현재 노드 : 1 / 인접한 노드들인 [2, 5, 9] 에서 방문하지 않은 노드는 [2, 5, 9]
   →  2에 방문
3. 현재 노드 : 2 / 현재 방문한 노드인 2를 visited 에 추가
   →  visited -> [1, 2]
4. 현재 노드 : 2 / 인접한 노드들인 [1, 3] 에서 방문하지 않은 노드는 [3]
   →  3에 방문
5. 현재 노드 : 3 / 현재 방문한 노드인 3을 visited 에 추가
   → visited -> [1, 2, 3]
6. 현재 노드 : 3 / 인접한 노드들인 [2, 4] 에서 방문하지 않은 노드는 [4]
   →  4에 방문
7. 현재 노드 : 4 / 현재 방문한 노드인 4를 visited 에 추가
   → visited -> [1, 2, 3, 4]
8. 현재 노드 : 4 / 인접한 노드인 [3] 에서 방문하지 않은 노드가 없다.
   →  이전에 방문했던 3으로 돌아감 (6번 과정)
9. 현재 노드 : 3 / 인접한 노드들인 [2, 4] 에서 방문하지 않은 노드가 없다.
   →  노드3 이전에 방문했던 2로 돌아감 (4번 과정)
10. 현재 노드 : 2 / 인접한 노드들인 [1, 3]에서 방문하지 않은 노드가 없다.
    →  노드2 이전에 방문했던 1로 돌아감 (2번 과정)
11. 현재 노드 : 1 / 인접한 노드들인 [2, 5, 9] 에서 방문하지 않은 노드는 [5, 9]
    →  5에 방문

이를 표로 나타내면 다음과 같다. 

단계	현재 노드	인접 노드	방문하지 않은 노드	행동	visited
1	1			현재 노드 visited에 추가	[1]
2	1	[2, 5, 9]	[2, 5, 9]	2에 방문	[1]
3	2			현재 노드 visited에 추가	[1, 2]
4	2	[1, 3]	[3]	3에 방문	[1, 2]
5	3			현재 노드 visited에 추가	[1, 2, 3]
6	3	[2, 4]	[4]	4에 방문	[1, 2, 3]
7	4			현재 노드 visited에 추가	[1, 2, 3, 4]
8	4	[3]	X	이전에 방문했던 노드로 돌아감 (6번 과정)	[1, 2, 3, 4]
9	3	[2, 4]	X	이전에 방문했던 노드로 돌아감 (4번 과정)	[1, 2, 3, 4]
10	2	[1, 3]	X	이전에 방문했던 노드로 돌아감 (2번 과정)	[1, 2, 3, 4]
11	1	[2, 5, 9]	[5, 9]	5에 방문	[1, 2, 3, 4]
12	5			현재 노드 visited에 추가	[1, 2, 3, 4, 5]

DFS 구현

• 노드를 방문하고 깊이 우선으로 인접한 노드를 방문한다.
• 또 그 노드를 방문해서 깊이 우선으로 인접한 노드를 방문한다.
• 위 과정을 반복한다.

👉 위의 예시 그래프를 재귀 방식, 스택 방식 두 가지로 구현해보자.

graph = {
    1: [2, 5, 9],
    2: [1, 3],
    3: [2, 4],
    4: [3],
    5: [1, 6, 8],
    6: [5, 7],
    7: [6],
    8: [5],
    9: [1, 10],
    10: [9]
}

재귀 방식

# recursive(재귀)

def dfs_recursive(graph, node, visited):
    # 방문처리
    visited.append(node)

    # 인접 노드 방문
    # 그래프 딕셔너리에서 1: [2, 5, 9] 일 때 1에 인접한 2,5,9를 차례로 가져옴
    for adj in graph[node]:
        if adj not in visited:
            dfs_recursive(graph, adj, visited)

    return visited

"""결과"""
dfs_recursive(graph, 1, []) # [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

스택 방식

• 인접한 노드 중 방문 안 한 게 없을 때, 최근 방문한 노드로 돌아가며 탐색하므로
• 후입선출 형태인 스택이 구현에 알맞다.

visited = [] # 방문한 목록
stack = [start] # 방문해야 하는 노드의 목록 (방문할 순서를 담아두는 용도)

으로 만들고,
위의 그래프에서는 1을 먼저 방문해야 하므로 start로 1을 담을 거다.
그러면 현재 노드가 1이고 그래프에서 1 : [2, 5, 9]이므로

visited = [1, 2] # 방문한 목록
stack = [2, 5, 9]

가 될 거고, 그럼 9를 먼저 방문하게 된다.

1 -> 9 를 방문했고 현재 노드가 9이라면, 그래프에서 1 : [2, 5, 9]이고 9: [1, 10] 이므로
해당 값([2, 5, 9], [1, 10])들을 stack에 넣어준다.

visited = [1, 9] # 방문한 목록
stack = [2, 5, 9, 1, 10]

그럼 이렇게 될 것이고, Stack 이기 때문에 1에 인접한 2나 5가 아닌 10을 먼저 방문하게 될 것이다.
이렇게 깊이 우선으로 탐색하게 구현할 수 있다.

# stack

def dfs_stack(graph, start):
    visited = [] # 방문한 목록
    stack = [start] # 방문해야 하는 노드의 목록 (방문할 순서를 담아두는 용도)

    # 방문할 노드가 남아있는 동안
    while stack:
        top = stack.pop() # 제일 최근에 삽입된 노드를 꺼내 (방문)
        visited.append(top) # 방문 완료

        # 인접 노드를 돌아 탐색
        for adj in graph[top]: # 인접 노드들이
            if adj not in visited: #방문한 적이 없다면
                stack.append(adj)

    return visited

"""결과"""
dfs_stack(graph, 1) # [1, 9, 10, 5, 8, 6, 7, 2, 3, 4]