dfs(깊이 우선 탐색) bfs(너비 우선 탐색)

dfs와 bfs는 그래프를 탐색하는 두가지 주요 알고리즘이다. 

깊이 우선 탐색 DFS

말 그대로 그래프의 깊이를 우선적으로 탐색하는 알고리즘이다. 시작 노드에서 시작해 깊이 들어가면서 그래프를 탐색하고, 더이상 탐색할 노드가 없다면 이전 노드로 되돌아와 똑같이 반복하여 탐색한다. DFS는 스택이나 재귀를 이용하여 구현한다. 

동작 과정

1. 시작 노드를 방문하고, 해당 노드를 방문한 것으로 표시 
2. 시작 노드와 연결된 이웃 노드 선택
3. 선택한 이웃노드가 방문되지 않은 경우, 그 이웃 노드를 새로운 시작 노드로 하여 DFS 재귀적으로 호출
4. 이웃 노드가 없을 때 까지 1-3 과정 반복 

위의 과정을 코드로 구현하면 이렇다. 

def dfs(graph, v, visited):
    visited[v] = True # 해당 노드 방문 처리 
    print(v, end=' ') 
    for i in graph[v]: # 해당 노드와 연결된 노드 
        if not visited[i]: # 연결된 노드가 방문한적 없다면
            dfs(graph, i, visited) # DFS 호출

너비 우선 탐색 BFS

그래프의 너비를 우선 탐색하는 알고리즘으로 시작 노드에서 시작해 해당 노드와 직접 연결된 모든 노드를 먼저 방문하고 방문한 노드와 연결된 다음 레벨의 모든 노드를 방문하는 방식을 반복해서 탐색한다. BFS는 큐를 사용해 구현한다. 

동작과정

1. 시작 노드를 방문하고, 해당 노드를 방문한 것으로 표시 
2. 시작 노드와 연결된 이웃 노드 선택해 큐에 추가
3. 큐에서 노드를 하나씩 꺼내어 방문하고, 해당 노드와 연결된 이웃 노드를 큐에 추가
4. 큐가 빌때까지 1-3 과정 반복 

코드 구현 

def bfs(graph, start, visited):
    que = deque([start]) # 시작 노드를 넣어 큐 생성
    visited[start] = True # 시작 노드 방문 처리 

    while que: 
        v = que.popleft() # 첫번째 값 꺼내고 
        print(v, end=' ')
        for i in graph[v]: # 해당 노드와 연결된 노드 
            if not visited[i]: # 연결된 노드 방문한 적 없다면
                que.append(i) # 큐에 넣고 방문처리 
                visited[i] = True

아래와 같은 그래프가 있다고 하면 깊이 우선은 1 >> 2 >> 4 >> 3 >> 5 순서로 death의 끝까지 들어갔다 나오는 방식이고, 너비 우선은 
1 >> 2 >> 3 >> 4 >> 5 순서로 순회하게 된다.(보통 작은 숫자부터 순회) 

이를 이용해 예제 문제를 하나 풀어보자.

백준의 1260번: DFS와 BFS

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

예제 입력 1 

4 5 1
1 2
1 3
1 4
2 4
3 4

예제 출력 1 

1 2 4 3
1 2 3 4

말그대로 bfs, dfs 구현해 방문 순서만 print 해주면 되는 문제이다. 여기서 처음에 헷갈렸던 것은 입력을 그래프로 어떻게 만들지 였는데, 먼저 그래프의 종류에는 크게 인접행렬과 인접리스트 두가지가 있다. 

인접행렬

인접행렬은 노드들을 2차원 배열로 표현 한 것이다. 노드 i, j가 연결 되어 있다면 배열의 (i, j) 위치와 (j, i)위치에 1이 저장되고 연결되어 있지 않다면 0이 저장되는 일종의 희소 행렬이다. 희소 행렬이기 때문에 연결 정보가 많이 않은 경우 대부분이 0을 가지고 있기 때문에 공간이 비효율적으로 사용 될 수 있다. 위의 예제 입력을 인접행렬로 표현하면 아래와 같다. 

[
    [0, 0, 0, 0, 0], # 0번 노드는 사용되지 않음
    [0, 0, 1, 1, 1], # 1번 노드는 2, 3, 4번 노드와 연결됨
    [0, 1, 0, 0, 1], # 2번 노드는 1, 4번 노드와 연결됨
    [0, 1, 0, 0, 1], # 3번 노드는 1, 4번 노드와 연결됨
    [0, 1, 1, 1, 0]  # 4번 노드는 1, 2, 3번 노드와 연결됨
]

인접 리스트

인접리스트는 각 노드에 연결된 노드의 리스트로 그래프를 표현하는 방식이다. 직접 연결된 노드 리스트만 가지고 있어서 인접행렬에 비해 공간 효율성이 높지만, 두 노드 연결을 확인 할때는 인접행렬에 비해 느리다. (인접행렬은 (i, j) 가 1이면 두 노드가 연결이 된 것을 바로 확인 할 수 있음) 위의 예제 입력을 인접 리스트로 표현하면 아래와 같다. 

[
    [],         # 0번 노드는 사용되지 않음
    [2, 3, 4],  # 1번 노드는 2, 3, 4번 노드와 연결됨
    [1, 4],     # 2번 노드는 1, 4번 노드와 연결됨
    [1, 4],     # 3번 노드는 1, 4번 노드와 연결됨
    [1, 2, 3]   # 4번 노드는 1, 2, 3번 노드와 연결됨
]

보통 인접리스트 방식을 사용해 문제를 풀기 때문에 입력을 받아 인접리스트 형태를 만들어 줬다. 
그래프를 2차원 배열로 껍데기를 만들고 1번 노드와 2번 노드가 연결 되어 있음을 저장하기 위해 1번 리스트에 2를 2번 리스트에 1을 넣어주는 코드이다. 정점 번호가 작은것 부터 순회하라고 했으므로 sort를 해준다. 

N, M, V = map(int, input().split())

graph = [[] for _ in range(N + 1)]

for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    
for i in graph:
    i.sort()

다음은 위의 bfs, dfs 코드와 동일한 함수를 이용해서 마저 구현하면 된다. visited는 방문 여부를 묻는 배열로 0 노드는 제외해야 하니까 N+1 개의 False 배열을 만들어 주고 요구사항에 맞춰 print 해주면 된다. 

visited = [False] * (N+1)
dfs(graph, V, visited)

print()

visited = [False] * (N+1)
bfs(graph, V, visited)

최종적으로 합친 코드는 다음과 같다. 

from collections import deque

N, M, V = map(int, input().split())

graph = [[] for _ in range(N + 1)]

for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

for i in graph:
    i.sort()

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

def bfs(graph, start, visited):
    que = deque([start])
    visited[start] = True

    while que:
        v = que.popleft()
        print(v, end=' ')
        for i in graph[v]:
            if not visited[i]:
                que.append(i)
                visited[i] = True

visited = [False] * (N+1)
dfs(graph, V, visited)

print()

visited = [False] * (N+1)
bfs(graph, V, visited)