[Algorithm] DFS/BFS

December 29, 2023

그래프 탐색 알고리즘 DFS/BFS

탐색(search)

많은 양의 데이터 중에서 원하는 데이터를 찾는 과정

대표적인 그래프 탐색 알고리즘으로는 DFS와 BFS가 있다.

DFS/BFS는 코딩 테스트에서 매우 자주 등장하는 유형이므로 반드시 숙지해야 한다.

DFS/BFS를 배우기 전에 반드시 스택과 큐는 반드시 알아두어야 할 자료구조이다.

Stack

먼저 들어 온 데이터가 나중에 나가는 형식의 자료구조 (선입후출) (FILO)
입구와 출구가 동일한 형태로 스택을 시각화할 수 있다.
ex) 쌓아올린 박스

스택 구현 예제

파이썬에서는 append()와 pop()의 시간복잡도가 상수. 즉 O(1)이기 때문에

리스트로 스택을 구현하면 된다.

stack = []

# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()

print(stack[::-1]) # 최상당 원소부터 출력
print(stack) # 최하단 원소부터 출력

# output
>>> [1, 3, 2, 5]
>>> [5, 2, 3, 1]

Queue

먼저 들어온 데이터가 먼저 나가는 형식의 자료구조 (선입선출) (FIFO)
입구와 출구가 모두 뚫려 있는 터널과 같은 형태
ex) 은행 창구, 터널 등

큐 구현 예제

파이썬에서는 큐를 구현할 때 deque를 사용하여 구현한다.

list자료형으로 기능적으로는 큐를 구현할 수 있지만 시간복잡도가 더 높아서 비효율적으로 동작한다.

from collections import deque

queue = deque()

# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()

print(queue) # 먼저 들어온 순서대로 출력
queue.reverse() # 역순으로 바꾸기
print(queue) # 나중에 들어온 원소부터 출력

# output
>>> deque([3, 7, 1, 4])
>>> deque([4, 1, 7, 3])

재귀 함수

재귀 함수(Recursive Function)

자기 자신을 다시 호출하는 함수를 의미

DFS를 실질적으로 구현하고자 할 때 자주 사용하는 방법 중 하나이므로 이해가 필요하다.

def recursive_func():
    print('재귀 함수 호출')
    recursive_func()

recursive_func()

파이썬에서는 재귀를 호출하는 과정에서의 깊이 제한이 있기 때문에 별다른 설정을 하지 않고 함수를 재귀적으로 호출하게 되면 오류가 발생한다.

def recursive_func():
    if i == 100:
        return
    print(i, '번째 재귀함수에서', i+1, '번째 재귀함수 호출')
    recursive_function(i+1)
    print(i, '번째 재귀함수 종료')

recursive_func(1)

재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수의 종료 조건을 반드시 명시해야 한다.

재귀함수 구현 예제(팩토리얼)

n! = 1 x 2 x 3 x ... x (n-1) x n

# 반복적으로 구현한 n!
def factorial_iterative(n):
    result = 1
    # 1부터 n까지 차례대로 곱하기
    for i in range(1, n+1):
        result += i
    return result

# 재귀적으로 구현한 n!
def factorial_recursive(n):
    if n <= 1: # n이 1이하인 경우 1 반환 -> 0!과 1!의 값은 1
        return 1 
    # n! = n * (n-1)!
    return n * factorial_recursive(n-1)

print('반복적으로 구현:', factorial_iterative(5))
print('재귀적으로 구현:', factorial_recursive(5))

# output
>>> 반복적으로 구현: 120
>>> 재귀적으로 구현: 120

재귀 함수 사용시 유의 사항

재귀 함수를 잘 활용하면 복잡한 알고리즘을 간결하게 작성할 수 있지만 오히려 다른사람이 이해하기 어려운 형태의 코드가 될 수도 있으므로 신중하게 사용
모든 재귀 함수는 반복문을 이용하여 동일한 기능을 구현할 수 있음
재귀 함수가 반복문보다 유리할 경우도 있고 불리한 경우도 있음
컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓임. 그래서 스택을 사용할 때 구현상 스택 라이브러리 대신에 재귀 함수를 이용하는 경우가 많음.

DFS

DFS

깊이 우선 탐색 (Depth-First Search)

그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

DFS는 스택이나 재귀함수를 이용하며 구체적인 동작 과정은 다음과 같다.

탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리하고, 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.

즉, 매번 최상단 원소를 기준으로 해서 방문하지 않은 인접 노드가 있으면 그 인접한 노드로도 방문을 수행하는 것이다.

그래프에서 가장 깊은 부분을 우선적으로 탐색하고 가장 깊게 들어갔다가 더 이상 들어갈 수 없다면 다른 방향으로 깊게 들어가는 방식을 반복 하는 것이다.

DFS 동작 예시

간선은 방향이 없는 무방향 그래프

DFS는 인접한 노드가 여러개 일 수 있기 때문에 어떤 노드부터 방문할지를 결정하기 위한 기준이 필요

이러한 방문 기준은 문제에서 요구하는 내용에 따라서 조금씩 달라질 수 있고 어떤 노드부터 방문하더라도 상관이 없는 경우도 있다.

[STEP 0] 그래프를 준비한다. (방문 기준: 번호가 낮은 인접 노드부터)

시작노드: 1

[STEP 1] 시작노드인 ‘1’을 스택에 삽입하고 방문 처리한다.

STACK = [1]

[STEP 2] 스택의 최상단 노드인 ‘1’에 방문하지 않은 인접 노드 ‘2’, ‘3’, ‘8’ 중 가장 작은 노드인 ‘2’를 스택에 넣고 방문 처리한다.

STACK = [2, 1]

[STEP 3] 스택의 최상단 노드인 ‘2’에 방문하지 않은 인접 노드 ‘7’번 노드를 스택에 넣고 방문 처리한다.

STACK = [7, 2, 1]

[STEP 4] 스택의 최상단 노드인 ‘7’에 방문하지 않은 인접 노드 ‘6’, ‘8’ 중 작은 노드인 ‘6’을 스택에 넣고 방문 처리한다.

STACK = [6, 7, 2, 1]

[STEP 5] 스택의 최상단 노드인 ‘6’에 방문하지 않은 인접 노드가 없다. 따라서 스택에서 ‘6’번 노드를 꺼낸다.

STACK = [7, 2, 1]

[STEP 6] 스택의 최상단 노드인 ‘7’에 방문하지 않은 인접 노드 ‘8’번 노드를 스택에 넣고 방문 처리한다.

STACK = [8, 7, 2, 1]

[STEP 7] 스택의 최상단 노드인 ‘8’에 방문하지 않은 인접 노드가 없으므로 ‘8’번 노드를 꺼낸다.

STACK = [7, 2, 1]

[STEP 8] 스택의 최상단 노드인 ‘7’에 방문하지 않은 인접 노드가 없으므로 ‘7’번 노드를 꺼낸다.

STACK = [2, 1]

[STEP 9] 스택의 최상단 노드인 ‘2’에 방문하지 않은 인접 노드가 없으므로 ‘2’번 노드를 꺼낸다.

STACK = [1]

[STEP 10] 스택의 최상단 노드인 ‘1’에 방문하지 않은 인접 노드 ‘3’번 노드를 스택에 넣고 방문 처리한다.

STACK = [3, 1]

[STEP 11] 스택의 최상단 노드인 ‘3’에 방문하지 않은 인접 노드 ‘4’, ‘5’ 중 작은 노드인 ‘4’번 노드를 스택에 넣고 방문 처리한다.

STACK = [4, 3, 1]

[STEP 11] 스택의 최상단 노드인 ‘4’에 방문하지 않은 인접 노드 ‘5’번 노드를 스택에 넣고 방문 처리한다.

STACK = [5, 4, 3, 1]

이러한 과정을 반복하였을 때 전체 노드의 탐색 순서(스택에 들어간 순서)는

1 -> 2 -> 7 -> 6 -> 8 -> 3 -> 4 -> 5

DFS 소스코드 예제 (Python)

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번 노드와 인접한 노드
    [1, 7],    # 2번 노드와 인접한 노드
    [1, 4, 5], # 3번 노드와 인접한 노드
    [3, 5],    # 4번 노드와 인접한 노드
    [3, 4],    # 5번 노드와 인접한 노드
    [7],       # 6번 노드와 인접한 노드
    [2, 6, 8], # 7번 노드와 인접한 노드
    [1, 7]     # 8번 노드와 인접한 노드
]

# 각 노드가 방문된 정보를 1차원 리스트로 표현
visited = [False] * 9

DFS 함수 호출

dfs(graph, 1, visited)

# output 
>>> 1 2 7 6 8 3 4 5

BFS

BFS

너비 우선 탐색 (Breadth-First Search)

그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘

BFS는 큐 자료구조를 이용하며, 구체적인 동작 과정은 다음과 같다.

탐색 시작 노드를 큐에 삽입하고 방문 처리 한다.
큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리 한다.
더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.

BFS 알고리즘은 특정 조건에서의 최단 경로 문제를 해결하기 위한 목적으로도 효과적으로 사용될 수 있다.

BFS 동작 예시

DFS와 동일하게 방향성이 없는 무방향 그래프

매번 큐에서 원소를 꺼내서 그 꺼낸 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 방문 처리 하는 것을 반복하면 된다.

[STEP 0] 그래프를 준비한다. (방문 기준: 번호가 낮은 인접 노드부터)

시작노드: 1

[STEP 1] 시작노드인 ‘1’을 큐에 삽입하고 방문 처리한다.

Queue = [1]

[STEP 2] 큐에서 노드 ‘1’을 꺼내 방문하지 않은 인접 노드 ‘2’, ‘3’, ‘8’을 큐에 삽입하고 방문 처리한다.

Queue = [8, 3, 2]

[STEP 3] 큐에서 노드 ‘2’를 꺼내 방문하지 않은 인접 노드 ‘7’을 큐에 삽입하고 방문 처리한다.

Queue = [7, 8, 3]

[STEP 4] 큐에서 노드 ‘3’을 꺼내 방문하지 않은 인접 노드 ‘4’, ‘5’를 큐에 삽입하고 방문 처리한다.

Queue = [5, 4, 7, 8]

[STEP 5] 큐에서 노드 ‘8’을 꺼내고 방문하지 않은 인접 노드가 없으므로 무시한다.

Queue = [5, 4, 7]

[STEP 6] 큐에서 노드 ‘7’을 꺼내 방문하지 않은 인접 노드 ‘6’을 큐에 삽입하고 방문 처리한다.

Queue = [6, 5, 4]

이러한 과정을 반복하였을 때 전체 노드의 탐색 순서(큐에 들어간 순서)는

1 -> 2 -> 3 -> 8 -> 7 -> 4 -> 5 -> 6

BFS 소스코드 예제 (Python)

BFS 메서드 정의

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

그래프 표현

# 각 노드가 연결된 정보를 2차원 리스트로 표현
graph = [
    [],
    [2, 3, 8], # 1번 노드와 인접한 노드
    [1, 7],    # 2번 노드와 인접한 노드
    [1, 4, 5], # 3번 노드와 인접한 노드
    [3, 5],    # 4번 노드와 인접한 노드
    [3, 4],    # 5번 노드와 인접한 노드
    [7],       # 6번 노드와 인접한 노드
    [2, 6, 8], # 7번 노드와 인접한 노드
    [1, 7]     # 8번 노드와 인접한 노드
]

# 각 노드가 방문된 정보를 1차원 리스트로 표현
visited = [False] * 9

BFS 함수 호출

bfs(graph, 1, visited)

# output
>>> 1 2 3 8 7 4 5 6

leejongseok

[Algorithm] DFS/BFS

Stack

Queue

재귀 함수

재귀 함수 사용시 유의 사항

DFS

DFS 동작 예시

DFS 소스코드 예제 (Python)

DFS 메서드 정의

그래프 표현

DFS 함수 호출

BFS

BFS 동작 예시

BFS 소스코드 예제 (Python)

BFS 메서드 정의

그래프 표현

BFS 함수 호출

Leave a comment

You may also enjoy

tistory로 이사 했습니다.

데이터분석 준전문가(ADsP) 후기(?)

[Baekjoon] 13909 - 창문 닫기 (Python)

[Baekjoon] 17103 - 골드바흐 파티션 (Python)