알고리즘(7) DFS, BFS

dongmin·2026년 3월 26일

BFS DFS 알고리즘

📌 그래프 탐색의 꽃, DFS(깊이 우선 탐색) 정리

1. 그래프(Graph)

노드(Node)와 그 노드들을 연결하는 간선(Edge)으로 이루어진 네트워크망 자료구조

2. 탐색(Search)

그래프 안에 있는 수많은 노드들을 특정 규칙에 따라 중복 없이, 한 번씩 빠짐없이 방문하는 과정

3. 🕳️깊이 우선 탐색 (DFS, Depth First Search)

DFS는 갈림길이 나타나면 특정 루트로 최대한 깊숙이 파고들어 탐색한 뒤, 막다른 곳에 도달하면 직전 갈림길로 되돌아와 다른 루트를 탐색하는 방식이다.

⚙️ DFS의 핵심 원리와 특징

DFS는 '가장 최근에 지나온 갈림길로 되돌아간다'는 특성 때문에, 가장 나중에 들어온 데이터가 먼저 나가는 후입선출(LIFO) 구조인 스택(Stack)과 유사하다.

사용 자료구조 : stack, 재귀함수
장점: 현재 경로상의 노드들만 기억하면 되므로 메모리를 적게 차지한다. 찾으려는 노드가 깊은 곳에 있다면 정답을 빠르게 찾을 수 있다.
단점: 정답이 없는 이상한 경로에 끝없이 빠질 수 있다. 또한 처음 발견한 정답이 최단 경로라는 보장이 없다.
주요 사용처: * 모든 경우의 수를 확인하되 조건에 안 맞으면 돌아가는 백트래킹 문제
- 이동하는 경로의 특징(순서, 가중치)을 기억해야 하는 문제
- 그래프 내의 사이클(순환) 존재 여부를 파악할 때

4. 🌊 너비 우선 탐색 (BFS, Breadth-First Search)

BFS는 시작 노드에서부터 가장 가까운 인접 노드들을 먼저 모두 탐색한 후, 그 다음으로 가까운 노드들을 탐색하며 점심적으로 넓게(Breadth) 퍼져나가는 방식이다.

⚙️ BFS의 핵심 원리와 특징

BFS는 '먼저 발견한 가까운 노드부터 순서대로 방문해야 한다'는 특성 때문에, 먼저 들어온 데이터가 먼저 나가는 선입선출(FIFO) 구조인 큐(Queue)를 반드시 사용해야 한다. (파이썬에서는 압도적인 속도를 위해 collections.deque를 사용한다.)

사용 자료구조: Queue (파이썬의 deque 라이브러리)
장점: 출발지에서 목표지점까지의 '최단 경로'를 무조건 보장한다. (가까운 곳부터 찾으므로, 목표를 발견하는 순간 그 거리가 곧 최단 거리다.)
단점: 탐색해야 할 노드가 많아지면 큐에 저장해야 하는 데이터가 급증하여 메모리를 많이 잡아먹는다.
주요 사용처:
- 미로 찾기나 지도에서 최단 거리(Shortest Path)를 구하는 문제
- "몇 번의 이동(또는 일수) 만에 도달할 수 있는가?"를 묻는 문제
- 시작점으로부터 주변으로 퍼져나가는 전염병, 바이러스, 영역 칠하기 문제

5. ⚔️ DFS vs BFS 한눈에 비교하기

DFS는 스택과 재귀함수를, BFS는 큐를 사용한다.
DFS는 최단경로를 보장하지 않지만 BFS는 최단경로를 보장한다
DFS는 메모리 사용이 적고 BFS는 메모리 사용이 많다.
DFS는 검색 속도가 BFS보다 느리다.
DFS는 경로의 특징 저장, 백트래킹 문제에 적합하고 BFS는 최단 거리 구하기, 최소 횟수 구하기에 적합하다.

6. DFS 구현

  graph = {
      'A' : ['B','C'],
      'B' : ['A','D','E'],
      'C' : ['A', 'F'],
      'D' : ['B'],
      'E' : ['B','F'],
      'F' : ['C','E']
  }

  def dfs_recursive(graph, start_node,visited=None):
    if visited is None:
      visited = []

    visited.append(start_node)

    for neighbor in graph[start_node]:
      if neighbor not in visited:
        dfs_recursive(graph, neighbor, visited)
    return visited

  print(dfs_recursive(graph,'A'))

7. BFS 구현

  from collections import deque

  graph = {
      'A': ['B', 'C'],
      'B': ['A', 'D', 'E'],
      'C': ['A', 'F'],
      'D': ['B'],
      'E': ['B', 'F'],
      'F': ['C', 'E']
  }

  def bfs_queue(graph, start_node):
      visited = [] # 방문한 노드를 기록
      queue = deque([start_node]) # queue는 방문할 예정인 노드를 담은 리스트. 중복해서 방문할 수 없음

      while queue:
          node = queue.popleft() # 방문하고자 하는 노드

          if node not in visited:
              visited.append(node) # visited에 node가 없으면 visited에 node 추가 -> node를 방문한 것

              queue.extend(graph[node]) # 방문한 노드와 인접한 노드를 큐에 저장

      return visited

  print("큐 BFS 방문 순서:", bfs_queue(graph, 'A'))