[알고리즘] 깊이 우선 탐색(DFS) 과 너비 우선 탐색(BFS)

미남잉·2021년 11월 28일
algorithmdatastructurepython
8

📌 강의 바로가기

개념과 코드, 이미지는 해당 책과 강의를 참고하였습니다.



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

탐색(Search)이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말합니다. 대표적인 그래프 탐색 알고리즘은 DFS와 BFS가 있습니다.

DFS와 BFS를 공부하기 전에 기초적으로 알아야 하는 자료구조 기초 개념이 있는데요. 그게 바로 스택과 큐, 재귀 함수입니다.

스택과 큐는 이전에 정리한 자료도 있으니 참고 부탁드립니다.

📌 스택
📌 큐



1. 스택 자료구조

먼저 들어 온 데이터가 나중에 나가는 형식(First In Last Out으로 FILO, 선입후출이라 함)의 자료구조입니다. 입구와 출구가 동일한 형태로 스택을 시각화 할 수 있습니다.

위 그림을 간단히 코드로 구현하면 아래와 같습니다.

삽입은 append로 삭제는 pop을 통해하면 삽입되는 데이터는 append를 통해 왼쪽부터 차례대로 쌓이고, 삭제되는 데이터는 pop을 통해 오른쪽 데이터부터 차례대로 빠집니다.

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) # 최하단 원소부터 출력
# 실행결과
[1, 3, 2, 5]
[5, 2, 3, 1]


2. 큐 자료구조

먼저 들어온 데이터가 먼저 나가는 형식(First In First Out으로 FIFO, 선입선출이라 함)의 자료구조입니다. 큐는 입구와 출구가 모두 뚫려 있는 터널과 같은 형태로 시각화 할 수 있습니다.

from collections import deque

# 큐(Queue) 구현을 위해 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) # 나중에 들어온 원서부터 출력

리스트만 이용해서 기능적으로 큐를 구현할 수 있지만 시간 복잡도가 더 높아서 비효율적으로 동작할 수 있기 때문에 deque 라이브러리를 사용한다고 합니다.

deque 라이브러리는 리스트와 동일하게 append가 사용 가능하며, 가장 왼쪽의 데이터를 꺼내고자 할 때 사용할 수 있는 popleft 메소드를 이용하여 데이터를 추출할 수 있습니다.

# 실행결과
deque([3, 7, 1, 4])
deque([4, 1, 7, 3])


3. 재귀함수

재귀 함수(Recursive Function)란 자기 자신을 다시 호출하는 함수를 의미합니다.

단순한 형태의 재귀함수 예제입니다.

  • '재귀 함수를 호출합니다' 라는 문자열을 무한히 출력합니다.
  • 어느 정도 출력하다가 최대 재귀 깊이 초과 메시지가 출력됩니다.
def recursive_function():
    print('재귀 함수를 호출합니다.')
    recursive_function()
    
recursive_function()

while이나 for문을 사용하지 않아도 어떠한 값을 무한대로 호출이 가능한 형태입니다.

재귀 함수를 문제 풀이에서 사용할 경우에는 재귀 함수의 종료 조건을 반드시 명시해주어야 합니다.

종료 조건을 제대로 명시하지 않으면 함수가 무한히 호출될 수 있기 때문입니다.

종료 조건을 포함한 재귀 함수 예제입니다

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

i에 1의 값이 들어갔으므로 99번 더 호출된 뒤 종료됩니다.


1) 팩토리얼 구현 예제

팩토리얼이란 n! = 1x2x3x ... x (n-1) x n이고 0!과 1!은 1입니다.

# 반복적으로 구현한 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을 반환
        return 1
    # n! = n * (n-1)!를 그대로 코드로 작성하기
    return n * factorial_recursive(n-1)

# 각각의 방식으로 구현한 n! 출력(n=5)
print('반복적으로 구현:', factorial_iterative(5))
print('반복적으로 구현:', factorial_recursive(5))
[실행 결과]
반복적으로 구현: 120
재귀적으로 구현: 120

2) 최대공약수 계산(유클리드 호제법) 예제

두 개의 자연수에 대한 최대공약수를 구하는 대표적인 알고리즘으로 유클리드 호제법이 있습니다.

유클리드 호제법

  • 두 자연수 A, B에 대해 (A > B) A를 B로 나눈 나머지를 R이라고 합시다.
  • 이때 A와 B의 최대공약수는 B와 R의 최대공약수와 같습니다.

유클리드 호제법의 아이디어를 그대로 재귀 함수로 작성할 수 있습니다.

예시: GCD(192, 162)

192에 162를 나누면 30이 되고, 이때 B인 162와 나머지 30의 최대공약수는 192와 162의 최대공약수와 같습니다.

다시 162에 30을 나누면 B인 30과 나머지 12가 남과 이의 최대공약수는 위의 경우와 같습니다.

마지막으로 30에 12을 나누고 B의 12, 나머지 6이 남습니다.

그러면 결과적으로 남은 6이 최대공약수가 됩니다.

이런식으로 계산하는 것이 유클리드 호제법이라 합니다.

def gcd(a, b):
    if a % b == 0:
        return b
    else:
        return gcd(b, a%b)
    
print(gcd(192, 162))
# 실행결과
6

재귀 함수를 잘 활용하면 복잡한 알고리즘을 간결하게 작성할 수 있습니다.

  • 단, 오히려 다른 사람이 이해하기 어려운 형태의 코드가 될 수 있으므로 신중히 사용해야 함

모든 재귀 함수는 반복문을 이용하여 동일한 기능을 구현할 수 있습니다.

재귀 함수가 반복문보다 유리한 경우도 있고 불리한 경우도 있습니다.

컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓이게 되는데, 스택을 사용해야 할 때 스택 라이브러리 대신 재귀 함수를 이용하는 경우가 많습니다.



DFS는 깊이 우선 탐색이라고 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘입니다.

DFS는 스택 자료구조(혹은 재귀함수)를 이용하며, 구체적인 동작 과정은 다음과 같습니다.

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

DFS 동작 예시

위의 노드의 경우 시작 노드가 '1'이며 낮은 번호부터 방문합니다.

1에게 2, 3, 8이 인접해 있는데 2를 방문합니다.

2는 7과 8 중 7을 방문 처리합니다.

7에게 인접한 노드는 6과 8이 있는데 이중에서 가장 작은 노드인 6을 스택에 넣습니다.

앞에선 6과 인접한 노드가 더 없었기 때문에 스택에 추가해주었고, 다시 초상단 노드 7로 이동 후 인접하지 않은 노드 8을 스택에 넣고 방문 처리합니다.

위의 탐색 과정을 반복하면 전체 노드의 탐색 순서(스택에 들어간 순서)는 다음과 같습니다.

탐색 순서: 1 -> 2 -> 7 -> 6 -> 8 -> 3 -> 4 -> 5

# 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,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

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

# 정의된 DFS 함수 호출
dfs(graph, 1, visited)

그래프 문제는 노드의 번호가 1번부터 시작하는 경우가 많기 때문에 graph에 인덱스 0인 경우의 리스트를 비워둡니다.

# 실행 결과
1 2 7 6 8 3 4 5


BFS는 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘입니다.

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

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

BFS 동작 예시

DFS와 같이 방문 기준에 따라 시작 노드에서부터 탐색을 시작합니다. 시작 노드는 1입니다.

큐에 1이 쌓였습니다.

큐의 특징에 따라 노드 1을 꺼내버리고 방문하지 않은 인접 노드 2, 3, 8을 큐에 삽입하고 방문처리합니다. 쌓이는 기준은 작은 숫자부터 쌓입니다.

이제 큐에서 2를 꺼내고 방문하지 않은 노드 7을 큐에 삽입합니다.

마찬가지로 큐에서 노드 3을 꺼내 방문하지 않은 인접 노드 4, 5를 큐에 삽입하고 방문 처리합니다.

이제 3을 꺼내면 큐에 8이 남기 때문에 8번 노드로 이동합니다.

큐에서 노드 8을 꺼내고 방문하지 않은 인접 노드가 없으므로 무시합니다.

마지막으로 7이 남았네요. 7로 가면 방문하지 않은 노드 6이 남았으므로 6을 방문처리하고 탐색이 끝납니다.

이러한 탐색 과정을 반복하여 전체 노드의 탐색 순서(큐에 들어간 순서)는 아래와 같습니다.

탐색 순서: 1 -> 2 -> 3 -> 8 -> 7 -> 4 -> 5 -> 6

BFS는 너비 우선 탐색 과정으로서 시작 노드부터 가까운 노드를 우선적으로 탐색하는 것을 알 수 있습니다.

시작 노드 1을 기준으로 거리가 1인 노드 2, 3, 8이 우선 방문되었고, 1로부터 거리가 2인 7, 4, 5가 그 다음, 거리가 3인 6이 마지막으로 방문되었습니다.

BFS는 이러한 특징 때문에 각 간선의 비용이 모두 동일한 상황에서 최단 거리를 해결하기 위한 목적으로 사용됩니다.

from collections import deque

# BFS 메서드 정의
def bfs(graph, start, visited):
    # 큐(Queue) 구현을 위해 deque 라이브러리 사용
    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]
]

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

# 정의된 DFS 함수 호출
bfs(graph, 1, visited)
# 실행 결과
1 2 3 8 7 4 5 6


6. 정리

  1. 스택과 큐의 개념
    • FILO, FIFO
    • deque 라이브러리
  2. 재귀 함수
    • 스택 라이브러리 대신 재귀 함수를 이용하기도 함
  3. DFS
    • 깊이 우선 탐색
    • 스택 자료구조(혹은 재귀함수)를 이용
  4. BFS
    • 너비 우선 탐색
    • 큐 자료구조를 이용
profile
미남잉
Tistory로 이사갔어요
이전 포스트

[알고리즘] 순차 탐색(Sequential Search)와 이진 탐색(Binary Search), 이진 탐색 트리

다음 포스트

[알고리즘] 정렬(Sorting) 요약 정리(선택, 삽입, 퀵, 계수정렬)

0개의 댓글