[알고리즘] DFS(Depth-First Search)와 BFS(Breadth-First Search)

0. Introduction

DFS와 BFS를 별도 게시물로 정리하려고 했으나 결국 하나의 게시물로 정리하게 되었다.

둘은 이름이 비슷해서인지 잘 헷갈리는 것 같다.

같은 게시물 안에서 동일한 그래프로 비교하면서 보면 더 잘 이해할 수 있을 것이라고 판단하였다.

단, BFS, DFS 문제풀이는 본 게시물에서 다루지 않는다. 앞으로 DFS, BFS 문제를 공부하면서 차근차근 하나씩 추가해보겠다.

 

1. DFS (Depth-First Search, 깊이 우선 탐색)

1. 정의

이름에서 알려주는 것처럼 깊이를 우선적으로, 즉, 가장 깊이 위치하는 노드까지 탐색하는 알고리즘이다.

DFS 문제를 풀 때는 스택을 활용하면 더 쉽게 해결할 수 있다.

이것은 예시를 보면 더욱 잘 이해할 수 있으니 예시를 함께 보면서 확인하도록 하자.

 

2. 동작 방식

DFS 동작 방법

1. 처음은 가장 작은 노드부터 시작한다. 방문한 노드 1은 스택에 저장한다. (1)

2. 인접 노드가 여러 개 있다면 그 중 가장 작은 노드로 이동한다. 위 이미지에서 1의 인접 노드는 2, 3으로 더 작은 것은 2 이므로 2로 이동한다. 마찬가지로 방문한 노드 2를 스택에 저장한다. (1->2)

3. 2의 인접 노드는 6과 7이다. 더 작은 6으로 이동하고, 스택에 6을 저장한다. (2->6)

4. 6의 인접 노드는 2와 7이다. 2가 더 작지만 이미 방문한 노드임을 알 수 있다. 따라서 7로 이동하고, 7을 스택에 저장한다. (6->7)

5. 7의 인접 노드는 2와 8이다. 마찬가지로 2가 더 작지만 이미 방문한 노드이므로 8로 이동하고, 8을 스택에 저장한다. (7->8)

6. 8에서 더 이상 인접 노드가 없으므로 뒤로 돌아간다. 내용이 길어 6-1, 6-2로 구분하겠다.

6-1. 8은 방문하지 않은 인접 노드가 없다. 따라서 스택에서 제거한다. 스택에서 하나씩 제거하며 뒤로 돌아간다. 뒤로 돌아가면서 방문하지 않은 인접 노드를 확인하고, 인접노드가 없으면 모두 제거한다. 현재 그래프에서는 2까지 방문하지 않은 인접노드가 없으므로 모두 제거해주었다. 

6-2. 1에서 방문하지 않은 노드 3이 있으므로 3으로 이동한다. (처음에 2, 3 중 2로 이동하였음) 3을 스택에 저장한다. (1->3)

7. 3은 인접 노드가 4와 5이고, 더 작은 4로 이동한다. 스택에 4를 저장한다. (3->4)

8. 4는 방문하지 않은 인접 노드가 없으므로 스택에서 제거되고, 3으로 돌아간다. 3은 방문하지 않은 인접노드 5가 있으므로, 5로 이동한다. (3->5)

 

따라서 최종적으로 그래프가 방문하는 순서는 1→2→6→7→8→3→4→5 순서가 된다.

 

지금 동작 방식을 자세히 살펴 보자. 만약 특정 노드에서 인접 노드가 없는 경우, 한 칸씩 뒤로 돌아가면서 확인한다.

이것은 다시 말하면 "최근에(=나중에)" 본 요소를 "먼저" 고려한다는 것이다. 어떤 자료구조와 비슷하지 않은가?

그렇다, 스택의 후입선출(LIFO) 구조와 동일하다. 따라서 앞서 말했듯 DFS 문제를 풀 때 스택을 통해 도움을 받을 수 있다.

 

3. 코드

# v: current node
def dfs(graph, v, visited):
    
    # 1. 지나간 노드 방문 처리
    visited[v] = True
    print(v, end=' ')

    # 2. 방문하지 않은 노드에 대해 다음 깊이 접근
    for x in graph[v]:
        if not visited[x]:
            dfs(graph, x, visited)

# graph: adjacency list
graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]
visited = [False]*9

dfs(graph, 1, visited)

 

 

재귀 함수의 호출 구조가 스택과 유사하기 때문에 별도의 자료구조 없이 재귀 함수의 호출만으로도 간단하게 BFS를 구현할 수 있다.

코드가 어떻게 동작하는지 이해가 잘 안 된다면 dfs(1)을 호출하는 것부터 손으로 적으며 알고리즘의 흐름을 따라가보는 것을 추천한다.

 

 

 

2. BFS (Breadth-First Search, 너비 우선 탐색)

1. 정의

DFS가 가장 깊이 위치하는 노드를 탐색했다면, BFS는 가장 가까이에 있는 노드부터 탐색하는 알고리즘이다.

마찬가지로 DFS가 후입선출 구조의 스택과 잘 어울렸다면, BFS는 선입선출 구조의 큐와 잘 어울린다.

이 또한 예시를 함께 살펴보며 이해해보도록 하자.

 

2. 동작 방식

BFS 동작 방법

1. 처음은 예외 없이 가장 작은 노드부터 시작한다. 방문한 노드는 큐에 저장한다. (1)

2. 방문한 노드의 인접한 노드를 모두 큐에 넣는다. (2, 3 /방문 순서는 숫자가 작은 순이다) 인접한 노드를 모두 큐에 넣은 현재 노드(1)는 큐에서 제거한다.

3. 다음 방문한 노드(2)의 인접 노드를 모두 큐에 넣는다. (6, 7) 2는 인접 노드를 모두 큐에 넣었으므로 큐에서 제거한다.

4. 다음 노드(3)의 인접 노드를 모두 큐에 넣는다. (4, 5) 3은 인접 노드를 모두 큐에 넣었으므로 큐에서 제거한다.

5. 다음 노드(6)는 방문하지 않은 인접 노드가 없으므로 큐에서 바로 제거한다.

6. 다음 노드(7)의 인접 노드를 큐에 넣는다. (8) 7은 인접 노드를 모두 큐에 넣었으므로 큐에서 제거한다.

이후. 현재 그림에서는 생략되었으나, 큐에 남은 아이템들도 돌면서 인접 노드가 있는지 확인하고 없으면 큐에서 제거되는 과정이 추가로 수행된다.

 

위 동작 방식을 통해 최종적으로 그래프가 방문하는 순서는 1→2→3→6→7→4→5→8 이다.

 

한 노드에 대해 깊이 탐색하고 다음 노드로 넘어갔던 DFS와 달리, 큐에 처리할 노드들을 줄 세워두고 순서대로 노드를 처리해간다.

줄 세워두고 순서대로 수행하는 것은 큐의 선입선출(FIFO) 구조와 동일하다.

 

3. 코드

from collections import deque

def bfs(graph, start, visited):
    visited[start] = True
    
    # BFS 실행을 위한 큐 생성
    q = deque([start])
    
    # 큐가 비어 있지 않은 경우 실행
    while q:
        v = q.popleft()
        print(v, end=' ')
        
        for x in graph[v]:
            # 현재 노드의 인접 노드 모두 큐에 추가
            if not visited[x]:
                q.append(x)
                visited[x] = True
        

# graph: adjacency list
graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]
visited = [False]*9

bfs(graph, 1, visited)

 

BFS는 큐와 함께 사용된다. 큐를 생성 후 시작 노드부터 큐에 아무 것도 들어있지 않을 때까지 돌면서 탐색을 수행한다.

가장 먼저 들어온 것부터 빼면서(popleft) 인접 노드를 모두 조사한다.

 

 

 

3. 마치며

BFS, DFS 두 알고리즘 모두 이름을 통해 동작 방식은 쉽게 이해할 수 있다.

BFS는 너비 우선 탐색, 즉 Breadth를 First로 보겠다는 거다. 현재 노드를 기준으로 넓게 먼저 본다는 의미이다.

DFS는 깊이 우선 탐색, Depth를 First로 보겠다는 것이니, 현재 노드를 기준으로 최대한 깊이 먼저 본다는 의미이다.

 

이처럼 의미는 잘 이해가 되었는데 여전히 문제에 적용하려니 아직 좀 헤매는 것 같다.

그래도 개념도 몰라서 가닥도 잡히지 않을 때보다는 희망이 보인다!

희망이 보이니 또 조금은 재미있는 것 같기도 하다.

 

기죽지 말고, 재미있게, 조금씩 차근차근 해보자! 화이팅!