DFS, BFS 알고리즘

오늘 소개할 알고리즘은 DFS, BFS 알고리즘이다. 각각은 깊이 우선 탐색, 너비 우선 탐색을 의미한다. 이는 그래프 자료구조를 탐색할 때 쓰이는 알고리즘들로 하나의 정점으로부터 시작하여 차례로 모든 정점들을 방문하는 방식이다.

---

1. DFS

우선 DFS를 살펴보자. DFS란 루트 노드에서 시작하여 다음 분기로 넘어가기 전, 해당 분기를 완벽하게 탐색하는 방법을 말한다. 즉, 탐색할 수 없는 지점을 만날 때까지 한 방향으로 계속 탐색 후, 막히게 될 경우 이전 분기로 돌아와 다른 방향으로 탐색하여 진행하는 방식이다. 전체 노드를 탐색할 때 유용하며, 재귀적 호출 형태를 지니고, BFS와 비교하여 간단하지만 더 느린 특징을 갖는다.

예시 코드를 살펴보자.

def dfs(graph, v, visited):
    visited[v] = True
    print(v, end = ' ')
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

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)

선언한 리스트를 살펴보자. graph는 노드들 간의 연결 관계를 표현한 리스트이다. 인덱스마다 해당 노드가 어떤 노드들과 연결되어 있는지 표현한다. 예를 들어 1번 노드의 경우 2, 3, 8번의 노드들과 연결되어 있음을 알 수 있다.

다음으로 visited 리스트이다. 인덱스가 노드의 번호가 되며 이에 따라 해당 노드의 방문 여부를 확인할 수 있다.

 

dfs 함수를 살펴보자. 파라미터로 graph, v, visited를 받는다. 여기서 v는 현재 위치한 노드를 의미한다.

현재 위치한 노드가 v이므로 visited 리스트에서 해당 인덱스의 값을 True로 바꿔준다. 즉, 방문 처리를 한다. 현재 위치한 노드가 어디인지 출력한 후, 해당 노드가 연결된 다른 노드들을 확인한다. 만약 연결된 노드를 방문한 기록이 없을 경우, 재귀를 통해 노드를 방문한다.

 

1번 노드부터 방문을 시작하여 전체 노드를 탐색할 수 있다.

---

그래프의 노드들간 간선 상태를 표현하면 다음 그림과 같다.

 

작성된 코드에 따른 방문은 다음과 같이 진행된다.

1. 1번 노드를 방문한다. 이 노드는 [2, 3, 8] 노드들과 연결되어 있다. 먼저 2번 노드를 방문한다.

2. 2번 노드를 방문한다. 이 노드는 [1, 7] 노드들과 연결되어 있다. 1번 노드는 방문했으므로 7번 노드를 방문한다.

3. 7번 노드를 방문한다. 이 노드는 [2, 6, 8] 노드들과 연결되어 있다. 2번 노드는 방문했으므로 6번 노드를 방문한다.

4. 6번 노드를 방문한다. 이 노드는 [7] 노드와 연결되어 있다. 7번 노드는 방문했고 더 이상 진행할 노드가 없으므로 함수가 종료되고 이전 함수로 돌아온다.

5. 7번 노드에서 다음 분기를 찾는다. 8번 노드에 방문하지 않았으므로 8번 노드를 방문한다.

6. 반복

 

해당 과정을 모두 마치고 나면 다음과 같은 결과가 출력된다.

1 2 7 6 8 3 4 5

이는 노드의 방문 순서를 의미한다.

---

2. BFS

다음으로 BFS를 살펴보자. BFS란 루트 노드에서 시작하여 인접한 노드를 먼저 탐색하는 방법을 말한다. 즉, 시작 정점으로부터 가까운 정점들을 먼저 방문하고 떨어져 있는 정점들을 나중에 방문하는 순회 기법이다. 최단 경로를 찾고자 할 때 유용하며, 큐(Queue)를 사용한다는 특징을 지녔다.

예시 코드를 살펴보자.

from collections import deque

def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = True
    while queue:
        v = queue.popleft()
        print(v, end = ' ')
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

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)

선언한 리스트들은 이전 DFS와 같다.

BFS는 큐를 이용하여 진행하므로 deque를 import 하였다.

 

선언해준 bfs 함수를 살펴보자. 파라미터로 graph, start, visited를 받는다. 여기서 start는 시작 노드를 의미한다. deque를 활용하여 시작 노드를 큐에 담아준다. 해당 노드를 방문처리한 후 큐가 비어있지 않을 경우 반복문이 지속되도록 한다.

반복문을 살펴보면 이러하다. 우선 큐에서 가장 먼저 들어간 노드를 팝 한다. 해당 노드를 출력한 뒤, graph에서 해당 노드 인덱스의 값들을 반복문을 활용하여 방문 여부를 확인한다. 만약 연결된 노드를 방문한 적이 없다면 그 노드를 큐에 추가한 뒤, 방문처리한다. 해당 과정을 완료하면 전체 노드를 탐색할 수 있다.

---

그래프의 노드들간 간선 상태는 DFS와 같다.

 

작성된 코드에 따른 방문은 다음과 같이 진행된다.

1. 1번 노드를 팝한다. 이 노드는 [2, 3, 8] 노드들과 연결되어 있다. 노드들 모두 방문한 적이 없으므로 방문 처리 후 큐에 추가한다.

Queue의 상태 : [2, 3, 8]

2. 2번 노드를 팝한다. 이 노드는 [1, 7] 노드들과 연결되어 있다. 1번 노드는 방문했으므로 7번 노드를 방문 처리 후 큐에 추가한다.

Queue의 상태 : [3, 8, 7]

3. 3번 노드를 팝한다. 이 노드는 [1, 4, 5] 노드들과 연결되어 있다. 1번 노드는 방문했으므로 4, 5번 노드를 방문 처리 후 큐에 추가한다.

Queue의 상태 : [8, 7, 4, 5]

4. 8번 노드를 팝한다. 이 노드는 [1, 7] 노드와 연결되어 있다. 1, 7번 노드는 방문했고 더 이상 진행할 노드가 없으므로 다음 반복을 진행하게 된다.

Queue의 상태 : [7, 4, 5]

5. 7번 노드를 팝한다. 이 노드는 [2, 6, 8] 노드와 연결되어 있다. 2, 8번 노드는 방문했으므로 6번 노드를 방문 처리 후 큐에 추가한다.

Queue의 상태 : [4, 5, 6]

6. 반복

 

해당 과정을 모두 마치고 나면 다음과 같은 결과가 출력된다.

1 2 3 8 7 4 5 6

 

이는 노드의 방문 순서를 의미한다.

---

이로써 DFS와 BFS의 동작 원리와 코드를 살펴보았다. 본인의 경험상 DFS보단 BFS를 활용하는 일이 더 많았다. BFS를 잘 익혀두도록 하자. 또한 코딩 테스트에서 구현, DFS, BFS, 그래프 문제들이 자주 출제되므로 더욱 익숙해질 수 있도록 해야 한다.