DFS (GRAPH)

DFS - Depth First Search

깊이 우선 검색

 

DFS

위와 같이 DFS는 움직인다.

DFS 표현

          2 - 3
          ⎜       
      0 - 1

**1. 이를 인접 행렬, 2차원 배열로 나타내면 다음과 같습니다!**
  0  1  2  3
0 X  O  X  X
1 O  X  O  X
2 X  O  X  O
3 X  X  O  X

이걸 배열로 표현하면 다음과 같습니다!
graph = [
    [False, True, False, False],
    [True, False, True, False],
    [False, True, False, True],
    [False, False, True, False]
]

**2. 이번에는 인접 리스트로 표현해보겠습니다!**
인접 리스트는 모든 노드에 연결된 노드에 대한 정보를 차례대로 다음과 같이 저장합니다.

0 -> 1
1 -> 0 -> 2
2 -> 1 -> 3
3 -> 2

이를 딕셔너리로 표현하면 다음과 같습니다!
graph = {
    0: [1],
    1: [0, 2]
    2: [1, 3]
    3: [2]
}

 

 

파이썬에서는 딕셔너리가 있어 해당 인접행렬을 딕셔너리로 표현한다.

 

 

DFS

위의 인접 행렬을 파이썬 딕셔너리로 표현하면 아래의 코드 graph와 같다.

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

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

    # 인접 노드 방문
    for adj in graph[node]:
        if adj not in visited:
            dfs_recursive(adj, visited)

    return visited
    
def dfs_stack(start):
    visited = []
    # 방문할 순서를 담아두는 용도
    stack = [start]

    # 방문할 노드가 남아있는 한 아래 로직을 반복한다.
    while stack:
        top = stack.pop()   # 스택의 값을 pop 한다.
        visited.append(top) # 해당값을 방문한 노드로 놓기위해 리스트에 넣는다.

        for adj in graph[top]:
            if adj not in visited:
                stack.append(adj)

    return visited

assert dfs_recursive(1, []) == [1, 2, 5, 6, 7, 3, 4]
assert dfs_stack(1) == [1, 4, 3, 5, 7, 6, 2]

DFS를 구현하는 방식은 2가지가 있다.

- recursive(재귀)

- stack

 

recursive 방식

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

    # 인접 노드 방문
    for adj in graph[node]:
        if adj not in visited:
            dfs_recursive(adj, visited)

    return visited

DFS, BFS 모두 방문 노드를 처리 해주어야한다.

 

recursive 함수는 시작노드와 방문한 노드를 넣어줄 리스트를 파라미터로 받아온다.

현재의 노드를 방문한 노드로 처리하기 위해 visited 리스트에 해당 노드를 넣어준다.

 

해당 노드를 key로 갖고 있는 graph의 딕셔너리의 value들을 차례로 돌며 체크해준다.

방문한 노드가 아니면 recursive 함수를 재귀로 계속해서 부른다.

 

ex) 시작노드가 1 이라면 딕셔너리 graph의 key 가 1인 value들인 2,3,4를 방문한다.

재귀를 코드로만 보면 이해하기 쉽지 않아 하나씩 살펴보자.

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

    # 인접 노드 방문
    for adj in graph[node]:
        if adj not in visited:
            dfs_recursive(adj, visited)

함수에서 함께 던져진 파라미터는 함수가 호출되는 순간 방문노드로 되어 visited 리스트에 들어간다.

재귀 함수 이므로 for문이 다 끝나기 전에 다시 재귀함수가 실행되어 또 for문 실행되고 해당 경우가 반복된다.

따라서 재귀함수는 해당 for문을 마친 후 이전의 for문으로 돌아가고 해당 for문 끝나면 다시 돌아간다.

재귀를 생각하는건 이러한 경우가 어려운거다

 

stack 방식

def dfs_stack(start):
    visited = []
    # 방문할 순서를 담아두는 용도
    stack = [start]

    # 방문할 노드가 남아있는 한 아래 로직을 반복한다.
    while stack:
        top = stack.pop()   # 스택의 값을 pop 한다.
        visited.append(top) # 해당값을 방문한 노드로 놓기위해 리스트에 넣는다.

        for adj in graph[top]:
            if adj not in visited:
                stack.append(adj)

    return visited

 

스택으로 구현하는 경우는 recursive와 다른 결과를 도출한다.

그 이유는 현재 방문한 노드를 바로 visited에 넣는게 아니라 stack이라는 리스트에 넣고 LIFO를 구현하기에 다른 결과값을 출력한다.

실제로 RECURSIVE의 로직을 생각하는게 쉽지 않다고 생각을 하지만 STACK과 비교했을 때 크게 다르지 않기에 stack을 구현했다면 반드시 recursive 방식으로도 구현을 해보는게 좋다고 생각을 한다.