[알고리즘] BFS/DFS 그리고 다익스트라 알고리즘 & 백트레킹
이전 포스팅을 참고
✒️ 1. BFS / DFS
- 너비우선탐색(Breadth-First Search, BFS)는 하나의 요소를 방문하고 그 요소에 인접한 모든 요소를 우선 방문하는 방식
- 깊이우선탐색(Depth-First Search, DFS)는 트리의 한 요소(노드)와 다음 수준(level)의 자식 노드를 따라가는 방향으로 탐색하는 방식
- 길 찾기 등에 주로 쓰이는 알고리즘이다. (미로 등)

✒️ 2. BFS (너비 우선 탐색)
BFS는 그래프나 트리 구조에서 노드를 탐색할 때 같은 레벨의 노드들을 먼저 탐색하는 방법이다.
시작 정점을 방문 한 후 시작 정점에 인접한 모든 정점들을 우선 방문한다.
더 이상 방문 할 정점이 없으면 한 depth 내려가서 다시 인접한 모든 정점들을 우선 방문한다.
💡 BFS의 특징
큐(Queue)를 사용하여 구현한다.
시작 노드로부터 가까운 노드를 먼저 방문하고 멀리 떨어져 있는 노드를 나중에 방문한다.
최단 경로 찾기 문제에 주로 사용된다.
메모리를 더 많이 사용할 수 있지만, 답이 되는 경로가 여러 개인 경우 최단경로임을 보장한다.
💡 아이디어
어떤 노드를 방문했었는지 여부를 반드시 검사(검사하지 않으면 무한루프)
visited = [] 로 놓는 편!
BFS는 방문한 노드들을 차례로 저장하고 꺼낼 수 있는 큐 사용(FIFO) => deque 사용

💡 deque 사용법
from collections import deque
# deque를 사용
queue = deque()
queue.append(1)
queue.append(2)
queue.popleft() # 1
💡 기본 템플릿
from collections import deque
def bfs(graph, start_node):
visited = set([start_node])
queue = deque([start_node])
while queue:
node = queue.popleft()
print(node, end=' ') # 노드 방문 처리
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
# 그래프 예시
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
bfs(graph, 'A')
💡 예시 문제
일단 2D 그리드나 매트릭스에서 상하좌우 이동을 처리할 때 매우 일반적이고 효율적인 방법으로
아래처럼 배열을 선언하는 방식을 알아두자.
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
[문제]
https://school.programmers.co.kr/learn/courses/30/lessons/159993
[풀이]
from collections import deque
def bfs(maps, start, end):
n, m = len(maps), len(maps[0])
queue = deque([(start[0], start[1], 0)]) # (x, y, distance)
visited = [[False] * m for _ in range(n)]
visited[start[0]][start[1]] = True
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
while queue:
x, y, dist = queue.popleft()
if (x, y) == end:
return dist
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if 0 <= nx < n and 0 <= ny < m and maps[nx][ny] != 'X' and not visited[nx][ny]:
visited[nx][ny] = True
queue.append((nx, ny, dist + 1))
return -1 # 도달할 수 없는 경우
def solution(maps):
n, m = len(maps), len(maps[0])
start, lever, end = None, None, None
for i in range(n):
for j in range(m):
if maps[i][j] == 'S':
start = (i, j)
elif maps[i][j] == 'L':
lever = (i, j)
elif maps[i][j] == 'E':
end = (i, j)
to_lever = bfs(maps, start, lever)
if to_lever == -1:
return -1
to_exit = bfs(maps, lever, end)
if to_exit == -1:
return -1
return to_lever + to_exit
✒️ 3. DFS (깊이 우선 탐색)
DFS는 그래프의 깊은 부분을 우선적으로 탐색하는 방법이다.
시작 정점을 방문 한 후 자식을 모두 탐색한다.
이때 연결된 노드가 존재하지 않을 때까지 들어왔다면 한 단계 이전으로 돌아가 다시 알고리즘을 수행한다.
💡 DFS의 특징
스택(Stack)이나 재귀를 사용하여 구현한다.
그래프의 깊은 부분을 우선적으로 탐색하며, 다시 돌아와서 다른 경로를 탐색한다.
모든 노드를 방문하고자 할 때 주로 사용한다.
-> BFS에 비해 구현은 좀 더 간단하지만 느리다.
경로의 특징을 저장해야 할 때 유용하다.
💡 아이디어
재귀적으로 동작(재귀 혹은 스택)
어떤 노드를 방문했었는지 여부를 반드시 검사(검사하지 않으면 무한루프)
이 또한 visited = [] 로 놓는 편!
💡 기본 템플릿 : 재귀 사용
def dfs_recursive(graph, node, visited=None):
if visited is None:
visited = set()
visited.add(node)
print(node, end=' ') # 노드 방문 처리
for neighbor in graph[node]:
if neighbor not in visited:
dfs_recursive(graph, neighbor, visited)
# 사용 예
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
dfs_recursive(graph, 'A') # 출력: A B D E F C
💡 기본 템플릿 : 스택 사용
파이썬의 리스트(list)는 스택의 기능을 모두 수행할 수 있다. => push() , pop()
def dfs_iterative(graph, start):
visited = set()
stack = [start]
while stack:
node = stack.pop()
if node not in visited:
visited.add(node)
print(node, end=' ') # 노드 방문 처리
# 인접 노드를 역순으로 스택에 추가 (순서를 맞추기 위해)
stack.extend(reversed([n for n in graph[node] if n not in visited]))
# 사용 예
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
dfs_iterative(graph, 'A') # 출력: A C F E B D
💡 예시 문제
[문제]
https://school.programmers.co.kr/learn/courses/30/lessons/154540
[풀이]
def dfs(maps, x, y, n, m):
if x < 0 or x >= n or y < 0 or y >= m or maps[x][y] == 'X':
return 0
food = int(maps[x][y])
maps[x][y] = 'X' # 방문 표시
# 상하좌우 탐색
for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nx, ny = x + dx, y + dy
food += dfs(maps, nx, ny, n, m)
return food
def solution(maps):
n, m = len(maps), len(maps[0])
stays = []
for i in range(n):
for j in range(m):
if maps[i][j] != 'X':
stays.append(dfs(maps, i, j, n, m))
return sorted(stays) if stays else [-1]
✒️ 4. 다익스트라(Dijkstra) 알고리즘 - 최단거리
💡 다익스트라 알고리즘
다익스트라 알고리즘은 BFS의 변형으로 볼 수 있다.
다익스트라 알고리즘은 하나의 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘이다.
음의 가중치가 없는 그래프에서 사용된다.
💡 아이디어
1. 거리와 노드를 튜플로 저장: (distance, node)
2. 거리가 가장 짧은 노드가 자동으로 힙의 최상위에 위치하게 된다.
3. heappop()으로 가장 가까운 노드를 효율적으로 선택할 수 있다.
cf. MST(무방향 가중치 그래프에서 모든 노드를 연결하는 가장 최소 비용의 트리를 찾는 문제)의 해결 알고리즘인 Prim 알고리즘도 heapq를 사용한다.
=> bfs 와 무엇이 다른가?
=> 다익스트라나 Prim 알고리즘에서 deque가 아닌 heapq를 사용하는 핵심 이유는 "가중치가 있는" 그래프에서 "최소" 값을 효율적으로 찾아야 하기 때문
💡 heapq 사용법
최소 힙(min heap) 자료구조를 사용
import heapq
# 1. 힙 생성
heap = []
# 2. 힙에 원소 추가
heapq.heappush(heap, 4)
heapq.heappush(heap, 1)
heapq.heappush(heap, 3)
heapq.heappush(heap, 2)
print("힙 상태:", heap) # 출력: [1, 2, 3, 4]
# 3. 힙에서 원소 제거 (최소값 추출)
min_value = heapq.heappop(heap)
print("추출된 최소값:", min_value) # 출력: 1
print("힙 상태:", heap) # 출력: [2, 4, 3]
# 4. 힙의 최소값 확인 (제거하지 않음)
min_value = heap[0]
print("현재 최소값:", min_value) # 출력: 2
# 5. 리스트를 힙으로 변환
numbers = [5, 7, 9, 1, 3]
heapq.heapify(numbers)
print("힙으로 변환된 리스트:", numbers) # 출력: [1, 3, 9, 7, 5]
💡 기본 템플릿
import heapq # 우선순위 큐 구현을 위한 heapq 모듈 임포트
def dijkstra(graph, start):
# 시작 노드로부터 각 노드까지의 거리를 저장할 딕셔너리 초기화
# 모든 노드의 거리를 무한대로 설정
distances = {node: float('inf') for node in graph}
# 시작 노드의 거리는 0으로 설정
distances[start] = 0
# 우선순위 큐 초기화: (거리, 노드) 튜플을 요소로 갖는 리스트
queue = [(0, start)]
while queue:
# 가장 거리가 짧은 노드 정보 꺼내기
current_distance, current_node = heapq.heappop(queue)
# 현재 노드가 이미 처리된 노드라면 스킵
# (더 짧은 경로를 통해 이미 처리된 경우)
if current_distance > distances[current_node]:
continue
# 현재 노드와 연결된 다른 인접 노드들 확인
for neighbor, weight in graph[current_node].items():
# 인접 노드로 가는 새로운 거리 계산
distance = current_distance + weight
# 새로운 거리가 기존에 알려진 거리보다 짧은 경우 갱신
if distance < distances[neighbor]:
distances[neighbor] = distance
# 갱신된 노드 정보를 우선순위 큐에 추가
heapq.heappush(queue, (distance, neighbor))
# 모든 노드까지의 최단 거리 반환
return distances
✒️ 5. 백트레킹
💡 백트레킹
백트래킹은 DFS를 기반으로 하지만, 유망하지 않은 경로를 조기에 차단하는 최적화 기법이다.
>> 무슨 뜻이면, 원하는 조건에 불일치 하면 이전 단계로 돌아가서 다음 경우의 수를 생각하는 방식이다.
DFS와 비슷하지만, DFS 는 가장 깊은 노드까지 무조건 탐색하지만,
백트레킹 방식은 불필요한 탐색을 하지 않고 바로 이전 단계로 넘어온다.
더욱 효율적이다.
💡 아이디어
def 재귀함수(n):
if 정답이면 :
출력 or 저장
else : 정답이 아니면 :
for 모든 자식 노드에 대해서:
if 정답에 유망하다면(답의 가능성이 있으면) :
자식노드로이동
재귀함수(n+1)
부모노드로 이동
위와 같이 DFS(재귀)에서 불필요한 탐색을 줄이기 위해 조건을 추가하는 방식!
💡 예시 문제
[문제]
https://school.programmers.co.kr/learn/courses/30/lessons/12952
가장 유명한 N-Queen 문제이다.
간단히 설명하면 "N*N 보드에 서로 공격할 수 없는 N개의 퀸을 둘 수 있는 경우의 수" 를 구하면 된다.
[풀이]
def solve_n_queens(N):
def is_safe(board, row, col):
# 같은 열에 퀸이 있는지 확인
for i in range(row):
# 같은 열이거나 대각선 상에 있는지 확인
if board[i] == col or \
board[i] - i == col - row or \ # 왼쪽 위 대각선
board[i] + i == col + row: # 오른쪽 위 대각선
return False
return True
def backtrack(row):
# 모든 행에 퀸을 배치했다면 해를 찾은 것
if row == N:
return 1
count = 0
for col in range(N):
if is_safe(board, row, col):
board[row] = col # 현재 위치에 퀸 배치
count += backtrack(row + 1) # 다음 행으로 이동
return count
# 각 행의 퀸 위치를 저장할 리스트 초기화
board = [-1] * N
return backtrack(0) # 첫 번째 행부터 시작