DFS(깊이우선탐색)과 BFS(너비우선탐색)

이해하기

 왼쪽과 같은 그래프가 있다고 하자. 깊이우선은 말그대로 옆에 노드가 있더라도 아래로 먼저 움직이고(깊게), 너비우선은 옆에 노드가 있으면 무조건 옆에 있는 노드로 움직인다고(넓게) 생각하면 된다.

 옆 그래프를 DFS하면 1 - 2 - 4 - 5 - 3 - 6 이 되고, BFS하면 1 - 2 - 3 - 4 - 5 - 6 이 된다.

 그렇다면 이 그래프를 코드로 나타내려면 어떻게 하면 될까?

 

 왼쪽처럼 배열로 나타낼 수 있다. 각 줄은 노드 한개를 의미한다. 1번 노드는 2, 3번과 연결되어 있기 때문에 1번째 줄에는 2, 3만 1이고, 2번 노드는 1, 4, 5번과 연결되어 있기 때문에 2번째 줄에는 1, 4, 5만 1이다.(양방향으로 가능한 노드일 경우 이렇다.)

 이 배열을 DFS, BFS하면 아래와 같다.

 

 

DFS일 때는 왼쪽과 같이 움직이게 된다. 1번 노드에서 시작해서 1번째 라인에서 시작한다. 1번째 라인을 차례대로 살펴보면 2, 3번 노드와 연결되어 있다는 것을 알 수 있다. 깊이우선이므로 2번 노드와 연결된 노드들을 탐색하기 위해 2번째 라인으로 간다. 2번 노드는 4, 5번과도 연결되어 있기 때문에 먼저 4번 노드로 가게 되고, 4번 노드는 더 연결된 노드가 없기 때문에 그 다음으로 5번 노드를 탐색하게 된다. 5번 노드도 연결된 노드가 없기 때문에(2번 노드와 연결된 노드들 모두 탐색) 2번 노드 다음인 3번 노드로 이동한다. 3번 노드는 6번 노드와 연결되어 있기 때문에 6번 노드로 이동하고, 더이상 연결된 노드가 없으므로 끝난다.

 

BFS일 때는 왼쪽과 같이 움직이게 된다. 1번 노드에서 시작해서 1번째 라인에서 시작한다. 1번째 라인을 차례대로 살펴보면 2, 3번 노드와 연결되어 있다는 것을 알 수 있고, 너비우선이므로 2번에서 3번으로 이동하고, 그 이후에 노드가 없으므로 2번 노드로 이동하게 된다. 2번 노드가 4, 5번과 연결되어 있으므로 4, 5번노드로 각각 이동하고, 4번 노드를 살펴보게 된다. 4번 노드는 더 이상 이웃한 노드가 없으므로 4번 다음 노드인 5번으로 이동하고, 5번 노드도 이웃한 노드가 없으므로(2번 노드에서 탐색 끝) 3번 노드로 이동하게 되고, 3번 노드를 따라 6번 노드로 이동하게 되고 더 이상 이웃한 노드나 연결된 노드가 없으므로 끝난다.

---

코드로 나타내기

import sys

# 정점의 개수 n, 간선의 개수 m, 정점의 번호 v
n, m, v = map(int, sys.stdin.readline().split())

matrix = [[0]*(n+1) for _ in range(n+1)]

for _ in range(m):
    point1, point2 = map(int, sys.stdin.readline().split())
    matrix[point1][point2] = 1
    matrix[point2][point1] = 1
    
visited = [] # 방문했던 노드를 담을 list

 먼저 DFS를 보자.

def dfs(start, visited):

    visited += [start]
    
    for i in range(len(matrix[start])): # 한 라인을 차례대로 탐색해서
    
        if matrix[start][i] == 1 and (i not in visited): # (아래 방향으로) 연결된 노드(방문은 안 했던)라면
        
            dfs(i, visited) # 그 노드의 (아래 방향으로) 연결된 노드의 또 연결된 노드를 탐색한다.
                            # 한 노드의 탐색이 끝나면 i는 +1되어 다음 연결된 노드로 넘어가게 된다.
            
    return visited

 그리고 BFS이다.

def bfs(start):

    visited = [start]
    queue = [start]
    
    while queue:
    
        n = queue.pop(0)
        
        for each in range(len(matrix[start])): # 한 라인을 차례대로 탐색해서
        
            if matrix[n][each] == 1 and (each not in visited): # 연결된 노드(방문은 안한)라면
            
                visited.append(each) # 방문한 노드에 넣어주고
                
                queue.append(each) # 큐에도 그 노드들을 넣어준다.
                                   # 이때 들어간 노드는 큐에서 꺼내져서
                                   # 그 노드의 라인을 탐색하는 데에 쓰인다.
                
    return visited