Algorithm - [ DFS / BFS ]

date

Jun 19, 2023

slug

algorithm-01

author

status

Public

DFS (Depth-First Search)

깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

DFS 는 어떻게 작동할까?

DFS 는 특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로를 탐색한다.

탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.

스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.

2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

⇒ 깊이 우선 탐색이라는 이름에서부터 알 수 있듯이 단순하게 가장 깊숙이 위치하는 노드에 닿을 때까지 확인하면 된다.

DFS 는 스택 자료 구조에 기초한다는 점에서 구현이 간단하다. 그런데 코드를 보면 스택을 쓰지 않고 재귀 함수로 구현을 한다.

이유는 컴퓨터 내부에서 재귀 함수의 수행은 스택 자료구조를 이용하기 때문이다.

다음의 예시를 보자.


def recursive_function(i):
# 100번째 호출을 했을 때 종료되도록 종료 조건 명시
    if i == 100:
        return
    print(i, '번째 재귀함수에서', i + 1, '번째 재귀함수를 호출합니다.')
    recursive_function(i + 1)
    print(i, '번째 재귀함수를 종료합니다.')

recursive_function(1)

함수를 계속 호출했을 때 가장 마지막에 호출한 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료된다.

컴퓨터의 구조 측면에서 보자면 연속해서 호출되는 함수는 메인 메모리의 스택 공간에 적재되므로 재귀 함수는 스택 자료구조와 같다.

⇒ 따라서 스택 자료구조를 활용해야 하는 상당수 알고리즘은 재귀 함수를 이용해서 간편하게 구현할 수 있다.

DFS 구현 예제


# dfs 메서드 정의
def dfs(graph, v, visited):
    visited[v] = True
    print(v, end=' ')
    
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

# 각 노드가 연결된 정보 2차원 배열
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)

⇒ 1 2 7 6 8 3 4 5

BFS (Breadth-First Search)

너비 우선 탐색이라는 의미를 가지며, 쉽게 말해 가까운 노드부터 탐색하는 알고리즘 (DFS 는 최대한 멀리 있는 노드를 우선 탐색하는 방식으로 동작)

BFS 는 어떤 방식으로 구현할 수 있을까?

선입선출 방식인 큐 자료 구조를 이용하여 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 먼저 들어온 것이 먼저 나가게 되어 가까운 노드부터 탐색을 진행한다.

탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.

큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.

2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

BFS 구현 예제


# queue 구현을 위해 deque 라이브러리 사용
from collections import deque

# bfs 메서드 정의
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

# 각 노드가 연결된 정보 2차원 배열
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)

⇒ 1 2 3 8 7 4 5 6

💡

Tip : 2차원 배열에서의 탐색 문제를 만나면 그래프 형태로 바꿔서 생각해 보자.

(출처: 이것이 코딩 테스트다)