[Python] DFS와 BFS

알고리즘 공부를 하는 중에 그래프 탐색 파트를 공부하기 시작해서 짚고 넘어가는 것이 좋겠다고 생각하여 DFS와 BFS를 알아보고, 파이썬으로 구현까지 해본다.

 

DFS (Depth-First Search)

• 깊이 우선 탐색이라고 부르고 그래프에서 깊은 부분을 우선 탐색하는 알고리즘이다.
• 갈 수 있는 한 맨 밑까지 탐색하여 리프노드(맨 아래 노드)를 방문하고, 이전 갈림길에서 선택하지 않은 노드들을 방문하는 식으로 탐색한다.
• 방문 위치를 기록 하는 스택을 이용하여 해결 할 수 있다.
• 또는 재귀로 해결 할 수 있다.

스택 방식 동작 과정

1. 탐색 시작 노드를 스택에 삽입하고 방문 배열에 방문 했다고 표시한다.
2. 스택의 최상단 노드에 방문 하지 않은 인접 노드가 있으면 해당 노드를 스택에 넣고 방문 처리를 한다.
3. 만약 방문하지 않은 인접 노드가 없다면 스택에서 최상단 노드를 꺼낸다.
4. 2번과 3번 과정을 스택이 빌 때 까지 진행한다. 

 

재귀 방식 동작 과정

1. 탐색 노드를 시작으로 탐색했던 노드들은 모두 방문 배열에 방문 했다고 표시한다.
2. 탐색 중인 노드 주변으로 방문 하지 않은 노드를 찾는다.
   1. 있다면 그 인접 노드를 함수의 인자로 넣어 재귀적으로 동작하도록 한다.
   2. 없다면 종료한다. 

graph = [
    [],
    [2, 5, 9],
    [1, 3],
    [4],
    [],
    [1, 6, 8],
    [5, 7],
    [6],
    [5],
    [1, 10],
    [9]
]
visited = [0] * 11

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

# 1 2 3 4 5 6 7 8 9 10 
# Process finished with exit code 0

 

장점

• 적은 공간 메모리 사용한다. (경로상의 노드만 기억하면 된다. BFS는 더 많은 노드를 기억 하고 있음)

단점

• 해가 없는 경로를 탐색할 경우 그 경로를 모두 탐색 할 때 까지 탐색한다. 따라서 효율성이 떨어진다.
• 최단 경로라는 보장이 없다.

 

BFS (Breadth-First Search)

• 너비 우선 탐색이라고 브로고, 탐색 노드로부터 제일 가까운 노드부터 탐색하는 알고리즘이다.
• 가까운 노드부터 우선 순위를 가져야 하기 때문에, 후입 선출 방식인 Queue를 사용하여 구현 할 수 있다.

 

동작 과정

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리한다.
2. 큐에서 노드를 꺼내고, 인접 노드들 중 방문 하지 않는 노드들을 모두 큐에 삽입하고 방문 처리한다.
3. 2번 과정을 반복한다.

 

from collections import deque
graph = [
    [],
    [2, 3, 4],
    [1, 5],
    [1, 6, 7],
    [1, 8],
    [2, 9],
    [3, 10],
    [3],
    [4],
    [5],
    [6]
]
visited = [0] * 11

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

bfs(1)

 

장점

• 모든 경로를 탐색 할 때 최단 경로를 보장한다.
• 노드 수가 적고 깊이가 얕은 해가 존재 할 때 유리하다.

단점

• 노드 수가 많을수록 탐색 가지가 급격히 증가함에 따라 보다 많은 메모리를 필요로 한다. 많은 노드를 저장하기 때문에 DFS보다 큰 공간 복잡도를 가진다.

 

 

 

적용하기

백준 1260번 DFS와 BFS

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 

from collections import deque
import sys
n, m, k = list(map(int, sys.stdin.readline().split()))

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

for _ in range(m):
    line = list(map(int, sys.stdin.readline().split()))
    graph[line[1]].append(line[0])
    graph[line[0]].append(line[1])

for node in graph:
    node.sort()

dfs_visited = [0] * (n+1)
dfs_ans = list()
def DFS(idx):
    dfs_visited[idx] = 1
    dfs_ans.append(idx)
    for i in graph[idx]:
        if not dfs_visited[i]:
            DFS(i)


bfs_visited = [0] * (n+1)
bfs_ans = list()
def BFS(idx):
    bfs_visited[idx] = 1
    q = deque()
    q.append(idx)
    while(q):
        node = q.popleft()
        bfs_ans.append(node)
        for i in graph[node]:
            if not bfs_visited[i]:
                q.append(i)
                bfs_visited[i] = 1

DFS(k)
BFS(k)

print(*dfs_ans)
print(*bfs_ans)