[Algorithm] DFS/BFS

꼭 필요한 자료구조 기초

• 탐색(Search)란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
  • 프로그래밍에서는 그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자루 자룸
  • 대표적인 탐색 알고리즘 : DFS, BFS
    • 이해하기 위해서는 스택, 큐에 대한 이해가 전제되어야 함
• 자료구조(Data Structure)란 데이터를 표현하고관리하고 처리하기 위한 구조
  • 스택, 큐 : 자료구조의 기초 개념
    • 삽입(Push) : 데이터를 삽입
    • 삭제(Pop) : 데이터를 삭제

스택

• 스택(Stack)은 선입 후출(First In Last Out) 구조 또는 후입 선출(Last In First Out) 구조
• 파이썬에서 스택을 이용할 때에는 별도의 라이브러리를 사용할 필요 없음
  • append(), pop() 메서드를 이용하면 스택 자료구조와 동일하게 동작

큐

• 큐(Queue)는 선입선출(First In Last Out) 구조
• 파이썬으로 큐를 구현할 때는 collections 모듈에서 제공하는 deque 자료구조를 활용
  • deque는 스택과 장점을 모두 채택한 것으로 데이터를 넣고 배는 속도가 리스트 자료형에 비해 효율적이며 queue 라이브러리를 이용하는 것보다 간단

재귀 함수

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

• 간단한 재귀함수 예시

    def recursive_function() :
    		print('재귀 함수를 호출합니다.')
    		recursive_function()
      
    recursive_function()
  

  • ‘재귀 함수를 호출합니다.’라는 문자열이 무한히 출력

재귀 함수의 종료 조건

• 재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수가 언제 끝날지, 종료 조건을 꼭 명시하여야 함
  • 조건을 주지 않으면 무한 호출이 되기때문

• 재귀 함수 종료 예시

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

2가지 방식으로 구현한 팩토리얼 예시

# 반복적으로 구현한 n!
def factorial_inerative(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! 출력
print('반복적으로 구현:', factorial_inerative(5))
print('재귀적으로 구현:', factorial_recursive(5))

• 반복문 대신 재귀 함수를 사용했을 때 얻을 수 있는 장점
  • 코드가 간결해짐 : 수학의 점화식(재귀식)을 사용하였기 때문
  • 특정한 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현 ⇒ 이 개념은 ‘다이나믹 프로그래밍’에서 중요하게 사용됨

탐색 알고리즘 DFS/BFS

DFS

• DFS는 Depth-First Search, 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
• 그래프(Graph)의 기본 구조를 알아야 함

  • 그래프는 노드(Node)와 간선(Edge)으로 표현되며 이때 노드를 정점(Vertex)라고도 함

    

  • 그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말함
  • 두 노드가 간선으로 연결되어 있다면 두 노드는 인접하다라고 표현
  • 프로그래밍에서 그래프는 크게 2가지 방식으로 표현
    • 인접 행렬(Adjacency Matrix) : 2차원 배열로 그래프의 연결 관계를 표현하는 방식
      • 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식
      • 연결되지 않는 노드끼리른 무한의 비용이라고 작성
    • 인접 리스트(Adjacecy List) : 리스트로 그래프의 연결 관계를 표현하는 방식
      • 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장

        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]
]

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

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

BFS

• BFS(Breadth First Search) 알고리즘은 ‘너비 우선 탐색’이라는 의미를 가짐
• 쉽게 말해 가까운 노드부터 탐색하는 알고리즘
• 동작 방식
  1. 탐색 시작 노드를 큐에 삽입하고 방문 처리
  2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 함
  3. 2번 과정을 더 이상 수행할 수 없을 때까지 반복

BFS 예제

from collections import deque

# BFS 메서드 정의
def bfs(graph, start, visited):
    # 큐 구현을 위해 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

# 정의된 BFS 함수 호출
bfs(graph, 1, visited)

정리

구분	DFS	BFS
동작 원리	스택	큐
구현 방법	재귀 함수 이용	큐 자료구조 이용