260115 BFS 너비우선탐색 알고리즘 완벽 가이드
15 Jan 2026
그래프와 트리를 탐색하는 가장 기본적이고 강력한 알고리즘 중 하나인 BFS를 마스터해보세요!
📚 목차
- BFS란 무엇인가?
- BFS 동작 원리
- 큐(Queue)의 역할
- 의사코드(Pseudocode)
- 다양한 언어 구현
- 시간/공간 복잡도 분석
- BFS vs DFS 비교
- 응용 분야
- Unity 게임 개발 활용
- 최적화 기법
- 실전 코딩 테스트 문제
- 트러블슈팅
- 참고 자료
🔍 BFS란 무엇인가?
📖 정의
BFS (Breadth-First Search, 너비 우선 탐색) 는 그래프나 트리 자료구조를 탐색하는 알고리즘입니다. 시작 노드에서 가까운 노드부터 차례대로 탐색하며, 레벨별로 탐색을 진행합니다.
🎨 핵심 개념
- 🌊 물결이 퍼지듯이 탐색이 진행됩니다
- 📏 최단 거리를 보장합니다 (가중치가 없는 그래프)
- 🎯 레벨 순서대로 방문합니다
- 📦 큐(Queue) 자료구조를 사용합니다
🏛️ 역사
BFS는 1959년 Edward F. Moore에 의해 처음 발표되었으며, 미로 탐색의 최단 경로를 찾기 위해 개발되었습니다. 이후 컴퓨터 과학의 기초 알고리즘으로 자리잡았습니다.
⚙️ BFS 동작 원리
🎬 단계별 동작 과정
1️⃣ 시작 노드를 큐에 넣고 방문 처리
2️⃣ 큐에서 노드를 하나 꺼냄
3️⃣ 꺼낸 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 넣고 방문 처리
4️⃣ 큐가 빌 때까지 2~3번 반복
🎨 시각적 표현 (ASCII 다이어그램)
그래프 예시:
1
/ \
2 3
/ \ \
4 5 6
탐색 순서:
Level 0: [1]
Level 1: [2, 3]
Level 2: [4, 5, 6]
큐 상태 변화:
Step 1: Queue = [1] Visited = {1}
Step 2: Queue = [2, 3] Visited = {1, 2, 3}
Step 3: Queue = [3, 4, 5] Visited = {1, 2, 3, 4, 5}
Step 4: Queue = [4, 5, 6] Visited = {1, 2, 3, 4, 5, 6}
Step 5: Queue = [5, 6] Visited = {1, 2, 3, 4, 5, 6}
Step 6: Queue = [6] Visited = {1, 2, 3, 4, 5, 6}
Step 7: Queue = [] Visited = {1, 2, 3, 4, 5, 6}
📊 Mermaid 다이어그램
graph TD
A[시작: 큐에 시작 노드 삽입] --> B[큐가 비어있는가?]
B -->|예| C[종료]
B -->|아니오| D[큐에서 노드 꺼내기]
D --> E[현재 노드 처리]
E --> F[인접 노드 확인]
F --> G[방문하지 않은 인접 노드를<br/>큐에 추가]
G --> H[방문 처리]
H --> B
style A fill:#e1f5ff
style C fill:#ffe1e1
style D fill:#fff4e1
style E fill:#e1ffe1
🔄 탐색 과정 애니메이션 (단계별)
Step 1: 초기 상태
Queue: [1]
Visited: {1}
Current: -
(1)
/ \
2 3
/ \ \
4 5 6
Step 2: 노드 1 방문
Queue: [2, 3]
Visited: {1, 2, 3}
Current: 1
[1]
/ \
(2) (3)
/ \ \
4 5 6
Step 3: 노드 2 방문
Queue: [3, 4, 5]
Visited: {1, 2, 3, 4, 5}
Current: 2
[1]
/ \
[2] (3)
/ \ \
(4) (5) 6
Step 4: 노드 3 방문
Queue: [4, 5, 6]
Visited: {1, 2, 3, 4, 5, 6}
Current: 3
[1]
/ \
[2] [3]
/ \ \
(4) (5) (6)
범례:
( ): 큐에 대기 중\[ \]: 방문 완료-
숫자 : 미방문
📦 큐(Queue)의 역할
🎯 왜 큐를 사용할까?
BFS는 FIFO (First In First Out) 원칙을 따릅니다. 먼저 발견한 노드를 먼저 탐색해야 레벨 순서를 보장할 수 있기 때문입니다.
📊 큐 vs 스택 비교
graph LR
subgraph "Queue (BFS)"
Q1[앞] --> Q2[2] --> Q3[3] --> Q4[4] --> Q5[뒤]
Q5 -.입력.-> Q5
Q1 -.출력.-> Q1
end
subgraph "Stack (DFS)"
S1[밑] --> S2[2] --> S3[3] --> S4[4] --> S5[위]
S5 -.입력/출력.-> S5
end
🔧 큐 구현 방법
Python - collections.deque
from collections import deque
queue = deque()
queue.append(1) # 뒤에 추가
node = queue.popleft() # 앞에서 제거
C# - Queue\<T\>
using System.Collections.Generic;
Queue<int> queue = new Queue<int>();
queue.Enqueue(1); // 뒤에 추가
int node = queue.Dequeue(); // 앞에서 제거
C++ - std::queue
#include <queue>
std::queue<int> queue;
queue.push(1); // 뒤에 추가
int node = queue.front(); // 앞 확인
queue.pop(); // 앞에서 제거
Java - LinkedList (Queue 인터페이스)
import java.util.Queue;
import java.util.LinkedList;
Queue<Integer> queue = new LinkedList<>();
queue.offer(1); // 뒤에 추가
int node = queue.poll(); // 앞에서 제거
📝 의사코드(Pseudocode)
기본 BFS 의사코드
BFS(graph, start_node):
create empty queue Q
create empty set visited
Q.enqueue(start_node)
visited.add(start_node)
while Q is not empty:
current = Q.dequeue()
// 현재 노드 처리
process(current)
// 인접 노드 탐색
for each neighbor of current in graph:
if neighbor not in visited:
visited.add(neighbor)
Q.enqueue(neighbor)
최단 거리 추적 BFS
BFS_with_distance(graph, start_node):
create empty queue Q
create distance map (node -> distance)
Q.enqueue(start_node)
distance[start_node] = 0
while Q is not empty:
current = Q.dequeue()
current_dist = distance[current]
for each neighbor of current in graph:
if neighbor not in distance:
distance[neighbor] = current_dist + 1
Q.enqueue(neighbor)
return distance
경로 추적 BFS
BFS_with_path(graph, start, goal):
create empty queue Q
create parent map (node -> parent_node)
Q.enqueue(start)
parent[start] = null
while Q is not empty:
current = Q.dequeue()
if current == goal:
return reconstruct_path(parent, start, goal)
for each neighbor of current in graph:
if neighbor not in parent:
parent[neighbor] = current
Q.enqueue(neighbor)
return null // 경로 없음
reconstruct_path(parent, start, goal):
path = []
current = goal
while current != null:
path.prepend(current)
current = parent[current]
return path
💻 다양한 언어 구현
🐍 Python 구현
기본 BFS (인접 리스트)
from collections import deque
from typing import List, Dict, Set
def bfs(graph: Dict[int, List[int]], start: int) -> List[int]:
"""
BFS 알고리즘 구현
Args:
graph: 인접 리스트로 표현된 그래프
start: 시작 노드
Returns:
방문 순서대로 정렬된 노드 리스트
"""
visited: Set[int] = set()
queue: deque = deque([start])
result: List[int] = []
visited.add(start)
while queue:
node = queue.popleft()
result.append(node)
# 인접 노드 탐색
for neighbor in graph.get(node, []):
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return result
# 사용 예제
if __name__ == "__main__":
# 그래프 정의
graph = {
1: [2, 3],
2: [1, 4, 5],
3: [1, 6],
4: [2],
5: [2],
6: [3]
}
result = bfs(graph, 1)
print(f"BFS 탐색 결과: {result}")
# 출력: BFS 탐색 결과: [1, 2, 3, 4, 5, 6]
최단 거리 계산 BFS
from collections import deque
from typing import Dict, List, Optional
def bfs_shortest_path(graph: Dict[int, List[int]],
start: int,
goal: int) -> Optional[List[int]]:
"""
BFS를 사용하여 최단 경로 찾기
Args:
graph: 인접 리스트로 표현된 그래프
start: 시작 노드
goal: 목표 노드
Returns:
최단 경로 리스트 (경로가 없으면 None)
"""
if start == goal:
return [start]
queue = deque([(start, [start])])
visited = {start}
while queue:
node, path = queue.popleft()
for neighbor in graph.get(node, []):
if neighbor not in visited:
new_path = path + [neighbor]
if neighbor == goal:
return new_path
visited.add(neighbor)
queue.append((neighbor, new_path))
return None
# 사용 예제
graph = {
1: [2, 3],
2: [1, 4, 5],
3: [1, 6],
4: [2, 7],
5: [2],
6: [3, 7],
7: [4, 6]
}
path = bfs_shortest_path(graph, 1, 7)
if path:
print(f"최단 경로: {' -> '.join(map(str, path))}")
print(f"거리: {len(path) - 1}")
# 출력:
# 최단 경로: 1 -> 2 -> 4 -> 7
# 거리: 3
그리드(2D 배열) BFS
from collections import deque
from typing import List, Tuple, Set
def bfs_grid(grid: List[List[int]],
start: Tuple[int, int],
goal: Tuple[int, int]) -> int:
"""
2D 그리드에서 BFS로 최단 거리 찾기
0: 이동 가능, 1: 벽
Args:
grid: 2D 그리드
start: 시작 좌표 (row, col)
goal: 목표 좌표 (row, col)
Returns:
최단 거리 (경로가 없으면 -1)
"""
rows, cols = len(grid), len(grid[0])
# 상하좌우 이동
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
queue = deque([(start[0], start[1], 0)]) # (row, col, distance)
visited: Set[Tuple[int, int]] = {start}
while queue:
row, col, dist = queue.popleft()
# 목표 도달
if (row, col) == goal:
return dist
# 4방향 탐색
for dr, dc in directions:
new_row, new_col = row + dr, col + dc
# 범위 체크
if 0 <= new_row < rows and 0 <= new_col < cols:
# 벽이 아니고 방문하지 않은 경우
if grid[new_row][new_col] == 0 and (new_row, new_col) not in visited:
visited.add((new_row, new_col))
queue.append((new_row, new_col, dist + 1))
return -1 # 경로 없음
# 사용 예제
if __name__ == "__main__":
maze = [
[0, 0, 1, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 1, 1, 0],
[0, 1, 0, 0, 0],
[0, 0, 0, 1, 0]
]
distance = bfs_grid(maze, (0, 0), (4, 4))
print(f"최단 거리: {distance}")
# 출력: 최단 거리: 8
🔷 C# 구현
기본 BFS
using System;
using System.Collections.Generic;
using System.Linq;
public class BFSAlgorithm
{
/// <summary>
/// BFS 알고리즘 구현
/// </summary>
/// <param name="graph">인접 리스트로 표현된 그래프</param>
/// <param name="start">시작 노드</param>
/// <returns>방문 순서대로 정렬된 노드 리스트</returns>
public static List<int> BFS(Dictionary<int, List<int>> graph, int start)
{
var visited = new HashSet<int>();
var queue = new Queue<int>();
var result = new List<int>();
queue.Enqueue(start);
visited.Add(start);
while (queue.Count > 0)
{
var node = queue.Dequeue();
result.Add(node);
// 인접 노드가 있는지 확인
if (graph.ContainsKey(node))
{
foreach (var neighbor in graph[node])
{
if (!visited.Contains(neighbor))
{
visited.Add(neighbor);
queue.Enqueue(neighbor);
}
}
}
}
return result;
}
// 사용 예제
public static void Main()
{
var graph = new Dictionary<int, List<int>>
{
{ 1, new List<int> { 2, 3 } },
{ 2, new List<int> { 1, 4, 5 } },
{ 3, new List<int> { 1, 6 } },
{ 4, new List<int> { 2 } },
{ 5, new List<int> { 2 } },
{ 6, new List<int> { 3 } }
};
var result = BFS(graph, 1);
Console.WriteLine($"BFS 탐색 결과: {string.Join(", ", result)}");
// 출력: BFS 탐색 결과: 1, 2, 3, 4, 5, 6
}
}
Unity용 BFS (Grid Pathfinding)
using UnityEngine;
using System.Collections.Generic;
public class UnityBFSPathfinding : MonoBehaviour
{
private struct Cell
{
public int Row;
public int Col;
public int Distance;
public Cell(int row, int col, int distance)
{
Row = row;
Col = col;
Distance = distance;
}
}
/// <summary>
/// Unity 그리드에서 BFS 경로 찾기
/// </summary>
/// <param name="grid">2D 그리드 (true: 이동 가능, false: 벽)</param>
/// <param name="start">시작 위치</param>
/// <param name="goal">목표 위치</param>
/// <returns>최단 경로 리스트</returns>
public List<Vector2Int> FindPath(bool[,] grid, Vector2Int start, Vector2Int goal)
{
var rows = grid.GetLength(0);
var cols = grid.GetLength(1);
// 4방향 이동 (상하좌우)
var directions = new Vector2Int[]
{
new Vector2Int(0, 1), // 오른쪽
new Vector2Int(1, 0), // 아래
new Vector2Int(0, -1), // 왼쪽
new Vector2Int(-1, 0) // 위
};
var queue = new Queue<Cell>();
var visited = new HashSet<Vector2Int>();
var parent = new Dictionary<Vector2Int, Vector2Int>();
queue.Enqueue(new Cell(start.x, start.y, 0));
visited.Add(start);
parent[start] = start;
while (queue.Count > 0)
{
var current = queue.Dequeue();
var currentPos = new Vector2Int(current.Row, current.Col);
// 목표 도달
if (currentPos == goal)
{
return ReconstructPath(parent, start, goal);
}
// 4방향 탐색
foreach (var dir in directions)
{
var newRow = current.Row + dir.x;
var newCol = current.Col + dir.y;
var newPos = new Vector2Int(newRow, newCol);
// 범위 체크
if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols)
{
// 이동 가능하고 방문하지 않은 경우
if (grid[newRow, newCol] && !visited.Contains(newPos))
{
visited.Add(newPos);
parent[newPos] = currentPos;
queue.Enqueue(new Cell(newRow, newCol, current.Distance + 1));
}
}
}
}
return null; // 경로 없음
}
/// <summary>
/// 부모 맵을 사용하여 경로 재구성
/// </summary>
private List<Vector2Int> ReconstructPath(Dictionary<Vector2Int, Vector2Int> parent,
Vector2Int start,
Vector2Int goal)
{
var path = new List<Vector2Int>();
var current = goal;
while (current != start)
{
path.Add(current);
current = parent[current];
}
path.Add(start);
path.Reverse();
return path;
}
// Unity 에디터에서 경로 시각화
private void OnDrawGizmos()
{
// 경로가 있다면 선으로 그리기
// (실제 사용 시 구현)
}
}
🔵 C++ 구현
기본 BFS
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
#include <unordered_map>
using namespace std;
/**
* BFS 알고리즘 구현
* @param graph 인접 리스트로 표현된 그래프
* @param start 시작 노드
* @return 방문 순서대로 정렬된 노드 벡터
*/
vector<int> bfs(unordered_map<int, vector<int>>& graph, int start) {
unordered_set<int> visited;
queue<int> q;
vector<int> result;
q.push(start);
visited.insert(start);
while (!q.empty()) {
int node = q.front();
q.pop();
result.push_back(node);
// 인접 노드 탐색
if (graph.find(node) != graph.end()) {
for (int neighbor : graph[node]) {
if (visited.find(neighbor) == visited.end()) {
visited.insert(neighbor);
q.push(neighbor);
}
}
}
}
return result;
}
// 사용 예제
int main() {
// 그래프 정의
unordered_map<int, vector<int>> graph;
graph[1] = {2, 3};
graph[2] = {1, 4, 5};
graph[3] = {1, 6};
graph[4] = {2};
graph[5] = {2};
graph[6] = {3};
vector<int> result = bfs(graph, 1);
cout << "BFS 탐색 결과: ";
for (int node : result) {
cout << node << " ";
}
cout << endl;
// 출력: BFS 탐색 결과: 1 2 3 4 5 6
return 0;
}
최단 거리 계산
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <climits>
using namespace std;
/**
* BFS를 사용한 최단 거리 계산
* @param graph 인접 리스트로 표현된 그래프
* @param start 시작 노드
* @return 각 노드까지의 최단 거리 맵
*/
unordered_map<int, int> bfs_shortest_distance(unordered_map<int, vector<int>>& graph, int start) {
unordered_map<int, int> distance;
queue<int> q;
q.push(start);
distance[start] = 0;
while (!q.empty()) {
int node = q.front();
q.pop();
int current_dist = distance[node];
if (graph.find(node) != graph.end()) {
for (int neighbor : graph[node]) {
if (distance.find(neighbor) == distance.end()) {
distance[neighbor] = current_dist + 1;
q.push(neighbor);
}
}
}
}
return distance;
}
int main() {
unordered_map<int, vector<int>> graph;
graph[1] = {2, 3};
graph[2] = {1, 4, 5};
graph[3] = {1, 6};
graph[4] = {2, 7};
graph[5] = {2};
graph[6] = {3, 7};
graph[7] = {4, 6};
auto distances = bfs_shortest_distance(graph, 1);
cout << "각 노드까지의 최단 거리:\n";
for (auto& [node, dist] : distances) {
cout << "노드 " << node << ": " << dist << "\n";
}
return 0;
}
☕ Java 구현
기본 BFS
import java.util.*;
public class BFSAlgorithm {
/**
* BFS 알고리즘 구현
* @param graph 인접 리스트로 표현된 그래프
* @param start 시작 노드
* @return 방문 순서대로 정렬된 노드 리스트
*/
public static List<Integer> bfs(Map<Integer, List<Integer>> graph, int start) {
Set<Integer> visited = new HashSet<>();
Queue<Integer> queue = new LinkedList<>();
List<Integer> result = new ArrayList<>();
queue.offer(start);
visited.add(start);
while (!queue.isEmpty()) {
int node = queue.poll();
result.add(node);
// 인접 노드 탐색
if (graph.containsKey(node)) {
for (int neighbor : graph.get(node)) {
if (!visited.contains(neighbor)) {
visited.add(neighbor);
queue.offer(neighbor);
}
}
}
}
return result;
}
// 사용 예제
public static void main(String[] args) {
Map<Integer, List<Integer>> graph = new HashMap<>();
graph.put(1, Arrays.asList(2, 3));
graph.put(2, Arrays.asList(1, 4, 5));
graph.put(3, Arrays.asList(1, 6));
graph.put(4, Arrays.asList(2));
graph.put(5, Arrays.asList(2));
graph.put(6, Arrays.asList(3));
List<Integer> result = bfs(graph, 1);
System.out.println("BFS 탐색 결과: " + result);
// 출력: BFS 탐색 결과: [1, 2, 3, 4, 5, 6]
}
}
그리드 BFS (최단 경로)
import java.util.*;
public class GridBFS {
static class Cell {
int row, col, distance;
Cell(int row, int col, int distance) {
this.row = row;
this.col = col;
this.distance = distance;
}
}
/**
* 2D 그리드에서 BFS로 최단 거리 찾기
* @param grid 2D 그리드 (0: 이동 가능, 1: 벽)
* @param start 시작 좌표
* @param goal 목표 좌표
* @return 최단 거리 (-1이면 경로 없음)
*/
public static int bfsGrid(int[][] grid, int[] start, int[] goal) {
int rows = grid.length;
int cols = grid[0].length;
// 4방향 이동
int[][] directions = {\{0, 1}, {1, 0}, {0, -1}, {-1, 0}\};
Queue<Cell> queue = new LinkedList<>();
boolean[][] visited = new boolean[rows][cols];
queue.offer(new Cell(start[0], start[1], 0));
visited[start[0]][start[1]] = true;
while (!queue.isEmpty()) {
Cell current = queue.poll();
// 목표 도달
if (current.row == goal[0] && current.col == goal[1]) {
return current.distance;
}
// 4방향 탐색
for (int[] dir : directions) {
int newRow = current.row + dir[0];
int newCol = current.col + dir[1];
// 범위 체크
if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols) {
// 벽이 아니고 방문하지 않은 경우
if (grid[newRow][newCol] == 0 && !visited[newRow][newCol]) {
visited[newRow][newCol] = true;
queue.offer(new Cell(newRow, newCol, current.distance + 1));
}
}
}
}
return -1; // 경로 없음
}
public static void main(String[] args) {
int[][] maze = {
{0, 0, 1, 0, 0},
{0, 0, 0, 0, 0},
{0, 0, 1, 1, 0},
{0, 1, 0, 0, 0},
{0, 0, 0, 1, 0}
};
int distance = bfsGrid(maze, new int[]{0, 0}, new int[]{4, 4});
System.out.println("최단 거리: " + distance);
// 출력: 최단 거리: 8
}
}
⏱️ 시간/공간 복잡도 분석
📊 시간 복잡도
O(V + E)
- V: 정점(Vertex)의 수
- E: 간선(Edge)의 수
분석
각 정점을 한 번씩 방문: O(V)
각 간선을 한 번씩 탐색: O(E)
총 시간 복잡도: O(V + E)
그래프 표현 방식에 따른 차이
<table header-row="true">
<tr>
<td>표현 방식</td>
<td>시간 복잡도</td>
<td>설명</td>
</tr>
<tr>
<td>**인접 리스트**</td>
<td>O(V + E)</td>
<td>효율적</td>
</tr>
<tr>
<td>**인접 행렬**</td>
<td>O(V²)</td>
<td>모든 정점에 대해 모든 간선 확인</td>
</tr>
</table>
💾 공간 복잡도
O(V)
사용 메모리
- 큐(Queue): 최악의 경우 모든 정점 저장 - O(V)
- 방문 배열(Visited): 모든 정점에 대한 방문 여부 - O(V)
- 결과 리스트: 모든 정점 저장 - O(V)
메모리 사용 예시
graph TD
A["메모리 사용량"]
B["Queue: O(V)"]
C["Visited Set: O(V)"]
D["Result List: O(V)"]
E["Total: O(V)"]
A --> B
A --> C
A --> D
B --> E
C --> E
D --> E
style A fill:#ffe1e1
style E fill:#e1ffe1
🔍 실제 성능 비교
다양한 그래프 크기에서의 실행 시간
import time
import random
from collections import deque, defaultdict
def measure_bfs_performance(num_vertices: int, num_edges: int):
# 랜덤 그래프 생성
graph = defaultdict(list)
for _ in range(num_edges):
u = random.randint(0, num_vertices - 1)
v = random.randint(0, num_vertices - 1)
if u != v:
graph[u].append(v)
# BFS 실행 및 시간 측정
start_time = time.time()
visited = set()
queue = deque([0])
visited.add(0)
while queue:
node = queue.popleft()
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
end_time = time.time()
elapsed = (end_time - start_time) * 1000 # 밀리초
return elapsed
# 성능 테스트
print("정점 수 | 간선 수 | 실행 시간 (ms)")
print("-" * 40)
for v in [100, 1000, 10000, 100000]:
e = v * 2 # 간선 수 = 정점 수 * 2
time_taken = measure_bfs_performance(v, e)
print(f"{v:7d} | {e:7d} | {time_taken:8.3f}")
예상 출력:
정점 수 | 간선 수 | 실행 시간 (ms)
----------------------------------------
100 | 200 | 0.234
1000 | 2000 | 2.156
10000 | 20000 | 23.789
100000 | 200000 | 267.453
⚖️ BFS vs DFS 비교
📊 핵심 차이점
<table header-row="true">
<tr>
<td>특성</td>
<td>BFS</td>
<td>DFS</td>
</tr>
<tr>
<td>**탐색 방식**</td>
<td>너비 우선 (레벨별)</td>
<td>깊이 우선 (경로 끝까지)</td>
</tr>
<tr>
<td>**자료구조**</td>
<td>큐 (Queue)</td>
<td>스택 (Stack) / 재귀</td>
</tr>
<tr>
<td>**시간 복잡도**</td>
<td>O(V + E)</td>
<td>O(V + E)</td>
</tr>
<tr>
<td>**공간 복잡도**</td>
<td>O(V)</td>
<td>O(h) - h는 최대 깊이</td>
</tr>
<tr>
<td>**최단 경로**</td>
<td>✅ 보장</td>
<td>❌ 보장 안 함</td>
</tr>
<tr>
<td>**메모리 사용**</td>
<td>넓은 그래프에서 많음</td>
<td>깊은 그래프에서 적음</td>
</tr>
<tr>
<td>**구현 방식**</td>
<td>반복문 (iterative)</td>
<td>재귀 or 반복문</td>
</tr>
</table>
🎨 시각적 비교
BFS 탐색 순서
1
/ \
2 3
/| |\
4 5 6 7
/|
8 9
BFS: 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9
레벨 0: [1]
레벨 1: [2, 3]
레벨 2: [4, 5, 6, 7]
레벨 3: [8, 9]
DFS 탐색 순서
1
/ \
2 3
/| |\
4 5 6 7
/|
8 9
DFS: 1 → 2 → 4 → 8 → 9 → 5 → 3 → 6 → 7
경로 우선 탐색
🔀 탐색 과정 비교 다이어그램
graph TD
subgraph "BFS - 레벨별 탐색"
B1["Level 0: Start"]
B2["Level 1: 인접 노드 모두"]
B3["Level 2: 다음 레벨 모두"]
B4["Level 3: ..."]
B1 --> B2 --> B3 --> B4
end
subgraph "DFS - 깊이 우선"
D1["Start"]
D2["첫 번째 자식"]
D3["그 자식의 자식"]
D4["끝까지 깊이 탐색"]
D5["백트래킹"]
D1 --> D2 --> D3 --> D4 --> D5
end
🎯 언제 어떤 알고리즘을 사용할까?
✅ BFS를 사용해야 할 때
- 최단 경로 찾기 (가중치 없는 그래프)
- 예: 미로 최단 경로, SNS 친구 추천
- 레벨 순서 탐색
- 예: 트리 레벨 순회, 조직도 계층 탐색
- 최소 이동 횟수
- 예: 게임에서 최소 이동, 퍼즐 문제
- 넓고 얕은 그래프
- 예: 소셜 네트워크, 웹 크롤링
✅ DFS를 사용해야 할 때
- 경로 존재 여부 확인
- 예: 미로 탈출 가능 여부
- 모든 경로 탐색
- 예: 백트래킹 문제, 순열/조합
- 사이클 검출
- 예: 순환 참조 확인
- 좁고 깊은 그래프
- 예: 파일 시스템 탐색
💡 실전 예제 비교
문제: 미로에서 출구까지의 최단 거리
from collections import deque
# BFS 솔루션 (최단 경로 보장)
def bfs_maze_shortest(maze, start, end):
queue = deque([(start, 0)]) # (위치, 거리)
visited = {start}
while queue:
pos, dist = queue.popleft()
if pos == end:
return dist # 최단 거리 보장!
for next_pos in get_neighbors(pos, maze):
if next_pos not in visited:
visited.add(next_pos)
queue.append((next_pos, dist + 1))
return -1
# DFS 솔루션 (최단 경로 보장 안 됨)
def dfs_maze_any(maze, start, end, visited=None):
if visited is None:
visited = set()
if start == end:
return 0 # 거리가 최단이 아닐 수 있음
visited.add(start)
for next_pos in get_neighbors(start, maze):
if next_pos not in visited:
result = dfs_maze_any(maze, next_pos, end, visited)
if result != -1:
return result + 1 # 첫 번째 경로 (최단 아님)
return -1
def get_neighbors(pos, maze):
# 상하좌우 이동 가능한 위치 반환
pass
결과 비교
미로:
S . . # .
# . # . .
. . . . #
. # # . E
BFS: 최단 거리 = 8
DFS: 거리 = 12 (첫 번째로 찾은 경로)
📈 성능 비교 차트
graph LR
subgraph "그래프 형태별 선호도"
A["넓고 얕은 그래프"] -.BFS 유리.-> B["O(V) 메모리"]
C["좁고 깊은 그래프"] -.DFS 유리.-> D["O(h) 메모리"]
end
subgraph "문제 유형별 선택"
E["최단 경로"] --> F["BFS"]
G["경로 존재 여부"] --> H["DFS"]
I["모든 경로 탐색"] --> H
J["레벨 순회"] --> F
end
🚀 응용 분야
BFS는 다양한 실전 문제에서 활용됩니다. 각 응용 분야를 자세히 살펴보겠습니다.
1️⃣ 최단 경로 찾기
📍 문제 설명
가중치가 없는 그래프에서 두 노드 사이의 최단 경로를 찾는 문제입니다.
💻 코드 예제
from collections import deque
from typing import List, Optional, Dict
def shortest_path(graph: Dict[int, List[int]], start: int, goal: int) -> Optional[List[int]]:
"""
BFS를 사용한 최단 경로 찾기
"""
if start == goal:
return [start]
queue = deque([start])
visited = {start}
parent = {start: None}
while queue:
node = queue.popleft()
for neighbor in graph.get(node, []):
if neighbor not in visited:
visited.add(neighbor)
parent[neighbor] = node
queue.append(neighbor)
# 목표 도달
if neighbor == goal:
# 경로 재구성
path = []
current = goal
while current is not None:
path.append(current)
current = parent[current]
return path[::-1]
return None # 경로 없음
# 사용 예제
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
path = shortest_path(graph, 'A', 'F')
print(f"최단 경로: {' -> '.join(path)}")
# 출력: 최단 경로: A -> C -> F
2️⃣ 레벨 순회 (Level Order Traversal)
📍 문제 설명
트리의 각 레벨별로 노드를 순회하는 문제입니다.
💻 코드 예제
from collections import deque
from typing import List, Optional
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def level_order_traversal(root: Optional[TreeNode]) -> List[List[int]]:
"""
이진 트리 레벨 순회
"""
if not root:
return []
result = []
queue = deque([root])
while queue:
level_size = len(queue)
current_level = []
# 현재 레벨의 모든 노드 처리
for _ in range(level_size):
node = queue.popleft()
current_level.append(node.val)
# 자식 노드를 큐에 추가
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(current_level)
return result
# 사용 예제
# 3
# / \
# 9 20
# / \
# 15 7
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
result = level_order_traversal(root)
print("레벨별 순회:", result)
# 출력: 레벨별 순회: [[3], [9, 20], [15, 7]]
3️⃣ 미로 탐색
📍 문제 설명
2D 그리드에서 시작점부터 도착점까지의 최단 경로를 찾는 문제입니다.
💻 코드 예제
from collections import deque
from typing import List, Tuple
def solve_maze(maze: List[List[int]],
start: Tuple[int, int],
end: Tuple[int, int]) -> int:
"""
미로 최단 경로 찾기
0: 통로, 1: 벽
"""
rows, cols = len(maze), len(maze[0])
# 4방향 이동 (상하좌우)
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
queue = deque([(start[0], start[1], 0)]) # (row, col, distance)
visited = {start}
while queue:
row, col, dist = queue.popleft()
# 도착점 도달
if (row, col) == end:
return dist
# 4방향 탐색
for dr, dc in directions:
new_row, new_col = row + dr, col + dc
# 범위 내, 통로, 미방문
if (0 <= new_row < rows and
0 <= new_col < cols and
maze[new_row][new_col] == 0 and
(new_row, new_col) not in visited):
visited.add((new_row, new_col))
queue.append((new_row, new_col, dist + 1))
return -1 # 경로 없음
# 사용 예제
maze = [
[0, 0, 0, 0, 1],
[1, 1, 0, 0, 0],
[0, 0, 0, 1, 0],
[0, 1, 1, 0, 0],
[0, 0, 0, 0, 0]
]
start = (0, 0)
end = (4, 4)
distance = solve_maze(maze, start, end)
print(f"최단 거리: {distance}")
# 출력: 최단 거리: 8
4️⃣ 소셜 네트워크 분석
📍 문제 설명
소셜 네트워크에서 사용자 간의 연결 거리를 계산하는 문제입니다.
💻 코드 예제
from collections import deque, defaultdict
from typing import Dict, List, Set
class SocialNetwork:
def __init__(self):
self.graph: Dict[str, Set[str]] = defaultdict(set)
def add_friendship(self, user1: str, user2: str):
"""친구 관계 추가"""
self.graph[user1].add(user2)
self.graph[user2].add(user1)
def degrees_of_separation(self, user1: str, user2: str) -> int:
"""
두 사용자 사이의 촌수(degrees of separation) 계산
"""
if user1 == user2:
return 0
if user1 not in self.graph or user2 not in self.graph:
return -1
queue = deque([(user1, 0)])
visited = {user1}
while queue:
current_user, degree = queue.popleft()
for friend in self.graph[current_user]:
if friend == user2:
return degree + 1
if friend not in visited:
visited.add(friend)
queue.append((friend, degree + 1))
return -1 # 연결되지 않음
def find_mutual_friends(self, user1: str, user2: str) -> List[str]:
"""공통 친구 찾기"""
if user1 not in self.graph or user2 not in self.graph:
return []
return list(self.graph[user1] & self.graph[user2])
def suggest_friends(self, user: str, max_suggestions: int = 5) -> List[str]:
"""
친구 추천 (친구의 친구 중 아직 친구가 아닌 사람)
"""
if user not in self.graph:
return []
direct_friends = self.graph[user]
suggestions = defaultdict(int)
# 친구의 친구 탐색
for friend in direct_friends:
for fof in self.graph[friend]: # friend of friend
if fof != user and fof not in direct_friends:
suggestions[fof] += 1
# 공통 친구 수 기준으로 정렬
sorted_suggestions = sorted(suggestions.items(),
key=lambda x: x[1],
reverse=True)
return [user for user, _ in sorted_suggestions[:max_suggestions]]
# 사용 예제
sn = SocialNetwork()
# 친구 관계 추가
sn.add_friendship("Alice", "Bob")
sn.add_friendship("Alice", "Charlie")
sn.add_friendship("Bob", "David")
sn.add_friendship("Charlie", "David")
sn.add_friendship("David", "Eve")
sn.add_friendship("Eve", "Frank")
# 촌수 계산
degree = sn.degrees_of_separation("Alice", "Frank")
print(f"Alice와 Frank의 촌수: {degree}")
# 출력: Alice와 Frank의 촌수: 4
# 공통 친구
mutual = sn.find_mutual_friends("Bob", "Charlie")
print(f"Bob과 Charlie의 공통 친구: {mutual}")
# 출력: Bob과 Charlie의 공통 친구: ['Alice', 'David']
# 친구 추천
suggestions = sn.suggest_friends("Alice")
print(f"Alice에게 추천할 친구: {suggestions}")
# 출력: Alice에게 추천할 친구: ['David']
5️⃣ 게임 AI (길찾기)
📍 문제 설명
게임에서 NPC가 장애물을 피해 목표 지점까지 이동하는 경로를 찾는 문제입니다.
💻 코드 예제
from collections import deque
from typing import List, Tuple, Optional
class GamePathfinding:
def __init__(self, grid: List[List[int]]):
"""
grid: 0 = 이동 가능, 1 = 장애물
"""
self.grid = grid
self.rows = len(grid)
self.cols = len(grid[0])
def find_path(self, start: Tuple[int, int],
goal: Tuple[int, int]) -> Optional[List[Tuple[int, int]]]:
"""
BFS를 사용한 경로 찾기
"""
# 4방향 이동
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
direction_names = ['→', '↓', '←', '↑']
queue = deque([start])
visited = {start}
parent = {start: None}
while queue:
current = queue.popleft()
if current == goal:
# 경로 재구성
path = []
node = goal
while node is not None:
path.append(node)
node = parent[node]
return path[::-1]
row, col = current
for dr, dc in directions:
new_row, new_col = row + dr, col + dc
new_pos = (new_row, new_col)
# 유효한 이동인지 확인
if (0 <= new_row < self.rows and
0 <= new_col < self.cols and
self.grid[new_row][new_col] == 0 and
new_pos not in visited):
visited.add(new_pos)
parent[new_pos] = current
queue.append(new_pos)
return None # 경로 없음
def visualize_path(self, path: List[Tuple[int, int]]):
"""
경로 시각화
"""
# 그리드 복사
visual = [row[:] for row in self.grid]
# 경로 표시
for i, (row, col) in enumerate(path):
if i == 0:
visual[row][col] = 'S' # Start
elif i == len(path) - 1:
visual[row][col] = 'G' # Goal
else:
visual[row][col] = '*' # Path
# 출력
for row in visual:
print(' '.join(str(cell) if cell != 1 else '█' for cell in row))
# 사용 예제
grid = [
[0, 0, 0, 0, 1, 0],
[0, 1, 1, 0, 1, 0],
[0, 0, 0, 0, 0, 0],
[0, 1, 1, 1, 1, 0],
[0, 0, 0, 0, 0, 0]
]
pathfinding = GamePathfinding(grid)
path = pathfinding.find_path((0, 0), (4, 5))
if path:
print(f"경로 길이: {len(path)}")
print("\n경로 시각화:")
pathfinding.visualize_path(path)
else:
print("경로를 찾을 수 없습니다.")
# 출력:
# 경로 길이: 11
#
# 경로 시각화:
# S * * * █ 0
# 0 █ █ * █ 0
# 0 0 0 * * *
# 0 █ █ █ █ *
# 0 0 0 0 0 G
6️⃣ 웹 크롤링
📍 문제 설명
웹 페이지의 링크를 따라가며 특정 깊이까지 페이지를 수집하는 문제입니다.
💻 코드 예제
from collections import deque
from typing import Set, List, Dict
import re
from urllib.parse import urljoin, urlparse
class WebCrawler:
def __init__(self, max_depth: int = 3):
self.max_depth = max_depth
self.visited: Set[str] = set()
def crawl(self, start_url: str) -> Dict[int, List[str]]:
"""
BFS를 사용한 웹 크롤링
"""
result = {}
queue = deque([(start_url, 0)]) # (url, depth)
self.visited.add(start_url)
while queue:
url, depth = queue.popleft()
# 깊이 제한
if depth > self.max_depth:
continue
# 현재 깊이에 URL 추가
if depth not in result:
result[depth] = []
result[depth].append(url)
# 링크 추출 (실제로는 HTML 파싱 필요)
links = self.extract_links(url)
for link in links:
if link not in self.visited:
self.visited.add(link)
queue.append((link, depth + 1))
return result
def extract_links(self, url: str) -> List[str]:
"""
페이지에서 링크 추출 (시뮬레이션)
실제로는 requests + BeautifulSoup 사용
"""
# 시뮬레이션용 더미 데이터
dummy_links = {
"
🎮 Unity 게임 개발 활용
Unity 게임 개발에서 BFS는 NPC AI, 길찾기, 타워 디펜스 등 다양한 분야에서 활용됩니다.
🗺️ Unity Grid Pathfinding
C# 구현
using UnityEngine;
using System.Collections.Generic;
public class UnityBFSPathfinder : MonoBehaviour
{
[System.Serializable]
public class GridCell
{
public Vector2Int Position;
public bool IsWalkable;
public GameObject VisualObject;
}
[Header("Grid Settings")]
public int gridWidth = 10;
public int gridHeight = 10;
public float cellSize = 1f;
[Header("Prefabs")]
public GameObject walkableCellPrefab;
public GameObject obstacleCellPrefab;
public GameObject pathMarkerPrefab;
private GridCell[,] grid;
private List<GameObject> pathMarkers = new List<GameObject>();
void Start()
{
InitializeGrid();
}
/// <summary>
/// 그리드 초기화
/// </summary>
void InitializeGrid()
{
grid = new GridCell[gridWidth, gridHeight];
for (int x = 0; x < gridWidth; x++)
{
for (int y = 0; y < gridHeight; y++)
{
var cell = new GridCell
{
Position = new Vector2Int(x, y),
IsWalkable = Random.value > 0.3f // 30% 확률로 장애물
};
// 시각적 표현
var prefab = cell.IsWalkable ? walkableCellPrefab : obstacleCellPrefab;
var worldPos = new Vector3(x * cellSize, 0, y * cellSize);
cell.VisualObject = Instantiate(prefab, worldPos, Quaternion.identity, transform);
grid[x, y] = cell;
}
}
}
/// <summary>
/// BFS 경로 찾기
/// </summary>
public List<Vector2Int> FindPath(Vector2Int start, Vector2Int goal)
{
if (!IsValidCell(start) || !IsValidCell(goal))
return null;
if (!grid[start.x, start.y].IsWalkable || !grid[goal.x, goal.y].IsWalkable)
return null;
// BFS 초기화
var queue = new Queue<Vector2Int>();
var visited = new HashSet<Vector2Int>();
var parent = new Dictionary<Vector2Int, Vector2Int>();
queue.Enqueue(start);
visited.Add(start);
parent[start] = start;
// 4방향 이동
Vector2Int[] directions = new Vector2Int[]
{
new Vector2Int(0, 1), // 위
new Vector2Int(1, 0), // 오른쪽
new Vector2Int(0, -1), // 아래
new Vector2Int(-1, 0) // 왼쪽
};
// BFS 탐색
while (queue.Count > 0)
{
var current = queue.Dequeue();
if (current == goal)
{
return ReconstructPath(parent, start, goal);
}
// 인접 셀 탐색
foreach (var dir in directions)
{
var next = current + dir;
if (IsValidCell(next) &&
grid[next.x, next.y].IsWalkable &&
!visited.Contains(next))
{
visited.Add(next);
parent[next] = current;
queue.Enqueue(next);
}
}
}
return null; // 경로 없음
}
/// <summary>
/// 경로 재구성
/// </summary>
private List<Vector2Int> ReconstructPath(Dictionary<Vector2Int, Vector2Int> parent,
Vector2Int start,
Vector2Int goal)
{
var path = new List<Vector2Int>();
var current = goal;
while (current != start)
{
path.Add(current);
current = parent[current];
}
path.Add(start);
path.Reverse();
return path;
}
/// <summary>
/// 유효한 셀인지 확인
/// </summary>
private bool IsValidCell(Vector2Int pos)
{
return pos.x >= 0 && pos.x < gridWidth &&
pos.y >= 0 && pos.y < gridHeight;
}
/// <summary>
/// 경로 시각화
/// </summary>
public void VisualizePath(List<Vector2Int> path)
{
// 이전 마커 제거
foreach (var marker in pathMarkers)
{
Destroy(marker);
}
pathMarkers.Clear();
// 새 경로 마커 생성
if (path != null)
{
foreach (var cell in path)
{
var worldPos = new Vector3(cell.x * cellSize, 0.5f, cell.y * cellSize);
var marker = Instantiate(pathMarkerPrefab, worldPos, Quaternion.identity, transform);
pathMarkers.Add(marker);
}
}
}
/// <summary>
/// 에디터에서 그리드 그리기
/// </summary>
void OnDrawGizmos()
{
if (grid == null) return;
for (int x = 0; x < gridWidth; x++)
{
for (int y = 0; y < gridHeight; y++)
{
var cell = grid[x, y];
var worldPos = new Vector3(x * cellSize, 0, y * cellSize);
Gizmos.color = cell.IsWalkable ?
</summary>
## 🤖 NPC AI Movement
### C# 구현
using UnityEngine;
using System.Collections;
using System.Collections.Generic;
public class NPCPathfollower : MonoBehaviour
{
[Header("Movement Settings")]
public float moveSpeed = 3f;
public float rotationSpeed = 5f;
public float waypointReachedDistance = 0.1f;
[Header("References")]
public UnityBFSPathfinder pathfinder;
public Transform target;
private List<Vector2Int> currentPath;
private int currentWaypointIndex = 0;
private bool isMoving = false;
void Update()
{
if (Input.GetMouseButtonDown(0))
{
FindAndFollowPath();
}
}
/// <summary>
/// 경로 찾기 및 이동 시작
/// </summary>
void FindAndFollowPath()
{
if (pathfinder == null || target == null)
return;
// 현재 위치와 목표 위치를 그리드 좌표로 변환
var startCell = WorldToGrid(transform.position);
var goalCell = WorldToGrid(target.position);
// 경로 찾기
currentPath = pathfinder.FindPath(startCell, goalCell);
if (currentPath != null && currentPath.Count > 0)
{
currentWaypointIndex = 0;
pathfinder.VisualizePath(currentPath);
StartCoroutine(FollowPath());
}
else
{
Debug.Log("경로를 찾을 수 없습니다!");
}
}
/// <summary>
/// 경로 따라 이동
/// </summary>
IEnumerator FollowPath()
{
isMoving = true;
while (currentWaypointIndex < currentPath.Count)
{
var targetCell = currentPath[currentWaypointIndex];
var targetWorldPos = GridToWorld(targetCell);
// 웨이포인트로 이동
while (Vector3.Distance(transform.position, targetWorldPos) > waypointReachedDistance)
{
// 이동
var direction = (targetWorldPos - transform.position).normalized;
transform.position += direction * moveSpeed * Time.deltaTime;
// 회전
if (direction !=
</summary>
## 🎯 타워 디펜스 예제
### 적이 최단 경로로 이동하는 시스템
using UnityEngine;
using System.Collections.Generic;
public class TowerDefenseEnemy : MonoBehaviour
{
[Header(“Movement”)]
public float moveSpeed = 2f;
[Header("Path")]
private List<Vector3> pathToGoal;
private int currentPathIndex = 0;
private UnityBFSPathfinder pathfinder;
void Start()
{
pathfinder = FindObjectOfType<UnityBFSPathfinder>();
FindPathToGoal();
}
void Update()
{
if (pathToGoal != null && currentPathIndex < pathToGoal.Count)
{
MoveAlongPath();
}
}
void FindPathToGoal()
{
var startCell = new Vector2Int(
Mathf.RoundToInt(transform.position.x / pathfinder.cellSize),
Mathf.RoundToInt(transform.position.z / pathfinder.cellSize)
);
// 목표 지점 (예: 맵 끝)
var goalCell = new Vector2Int(pathfinder.gridWidth - 1, pathfinder.gridHeight - 1);
var path = pathfinder.FindPath(startCell, goalCell);
if (path != null)
{
pathToGoal = new List<Vector3>();
foreach (var cell in path)
{
pathToGoal.Add(new Vector3(
cell.x * pathfinder.cellSize,
transform.position.y,
cell.y * pathfinder.cellSize
));
}
}
}
void MoveAlongPath()
{
var targetPos = pathToGoal[currentPathIndex];
transform.position = Vector3.MoveTowards(transform.position, targetPos, moveSpeed * Time.deltaTime);
// 방향 회전
var direction = (targetPos - transform.position).normalized;
if (direction != ```
(계속 작성 중… 다음 섹션: 최적화 기법)
⚡ 최적화 기법
BFS의 기본 구현은 효율적이지만, 특정 상황에서는 추가 최적화가 필요합니다.
🔄 양방향 BFS (Bidirectional BFS)
📍 개념
양방향 BFS는 시작점과 목표점에서 동시에 탐색을 시작하여, 두 탐색이 만나는 지점을 찾는 기법입니다.
📊 시간 복잡도 개선
- 일반 BFS: O(b\^d)
- 양방향 BFS: O(b\^(d/2))
여기서 b는 분기 계수(branching factor), d는 깊이입니다.
💻 Python 구현
from collections import deque
from typing import Dict, List, Optional, Set
def bidirectional_bfs(graph: Dict[int, List[int]],
start: int,
goal: int) -> Optional[List[int]]:
"""
양방향 BFS 구현
"""
if start == goal:
return [start]
# 전방 탐색 (시작점에서)
forward_queue = deque([start])
forward_visited = {start: None}
# 후방 탐색 (목표점에서)
backward_queue = deque([goal])
backward_visited = {goal: None}
while forward_queue and backward_queue:
# 전방 탐색 1단계
meeting_point = bfs_step(graph, forward_queue, forward_visited, backward_visited)
if meeting_point is not None:
return construct_bidirectional_path(forward_visited, backward_visited, start, goal, meeting_point)
# 후방 탐색 1단계
meeting_point = bfs_step(graph, backward_queue, backward_visited, forward_visited)
if meeting_point is not None:
return construct_bidirectional_path(forward_visited, backward_visited, start, goal, meeting_point)
return None # 경로 없음
def bfs_step(graph: Dict[int, List[int]],
queue: deque,
visited: Dict[int, Optional[int]],
other_visited: Dict[int, Optional[int]]) -> Optional[int]:
"""
BFS 한 단계 실행
"""
if not queue:
return None
node = queue.popleft()
for neighbor in graph.get(node, []):
# 다른 쪽 탐색과 만남
if neighbor in other_visited:
return neighbor
# 아직 방문하지 않은 노드
if neighbor not in visited:
visited[neighbor] = node
queue.append(neighbor)
return None
def construct_bidirectional_path(forward_visited: Dict[int, Optional[int]],
backward_visited: Dict[int, Optional[int]],
start: int,
goal: int,
meeting_point: int) -> List[int]:
"""
양방향 탐색 결과로 경로 구성
"""
# 전방 경로 (시작 -> 만남점)
forward_path = []
node = meeting_point
while node is not None:
forward_path.append(node)
node = forward_visited[node]
forward_path.reverse()
# 후방 경로 (만남점 -> 목표)
backward_path = []
node = backward_visited[meeting_point]
while node is not None:
backward_path.append(node)
node = backward_visited[node]
# 경로 합치기
return forward_path + backward_path
# 사용 예제
graph = {
1: [2, 3],
2: [1, 4, 5],
3: [1, 6, 7],
4: [2, 8],
5: [2, 8],
6: [3, 9],
7: [3, 9],
8: [4, 5, 10],
9: [6, 7, 10],
10: [8, 9]
}
path = bidirectional_bfs(graph, 1, 10)
print(f"양방향 BFS 경로: {' -> '.join(map(str, path))}")
# 출력: 양방향 BFS 경로: 1 -> 2 -> 4 -> 8 -> 10
📊 성능 비교
import time
from collections import deque, defaultdict
import random
def compare_bfs_performance(num_nodes: int):
# 랜덤 그래프 생성
graph = defaultdict(list)
for i in range(num_nodes):
for _ in range(random.randint(1, 5)):
neighbor = random.randint(0, num_nodes - 1)
if neighbor != i:
graph[i].append(neighbor)
start, goal = 0, num_nodes - 1
# 일반 BFS
start_time = time.time()
bfs_shortest_path(graph, start, goal)
bfs_time = (time.time() - start_time) * 1000
# 양방향 BFS
start_time = time.time()
bidirectional_bfs(graph, start, goal)
bi_bfs_time = (time.time() - start_time) * 1000
print(f"노드 수: {num_nodes}")
print(f" 일반 BFS: {bfs_time:.3f}ms")
print(f" 양방향 BFS: {bi_bfs_time:.3f}ms")
print(f" 성능 향상: {(bfs_time / bi_bfs_time):.2f}x\n")
for nodes in [100, 500, 1000, 5000]:
compare_bfs_performance(nodes)
💰 0-1 BFS
📍 개념
0-1 BFS는 간선의 가중치가 0 또는 1만 있는 그래프에서 최단 경로를 찾는 최적화 기법입니다.
💡 핵심 아이디어
- 가중치 0인 간선: 덱(deque)의 앞에 삽입
- 가중치 1인 간선: 덱의 뒤에 삽입
💻 Python 구현
from collections import deque
from typing import Dict, List, Tuple
import math
def zero_one_bfs(graph: Dict[int, List[Tuple[int, int]]], start: int) -> Dict[int, int]:
"""
0-1 BFS 구현
graph: {node: [(neighbor, weight), ...]}
weight는 0 또는 1만 가능
Returns:
각 노드까지의 최단 거리
"""
distances = {node: math.inf for node in graph}
distances[start] = 0
dq = deque([start])
while dq:
node = dq.popleft()
for neighbor, weight in graph.get(node, []):
new_dist = distances[node] + weight
if new_dist < distances[neighbor]:
distances[neighbor] = new_dist
if weight == 0:
# 가중치 0: 앞에 삽입
dq.appendleft(neighbor)
else:
# 가중치 1: 뒤에 삽입
dq.append(neighbor)
return distances
# 사용 예제
graph = {
1: [(2, 0), (3, 1)], # 1->2 가중치 0, 1->3 가중치 1
2: [(4, 1), (5, 0)], # 2->4 가중치 1, 2->5 가중치 0
3: [(6, 0)], # 3->6 가중치 0
4: [(7, 0)],
5: [(7, 1)],
6: [(7, 1)],
7: []
}
distances = zero_one_bfs(graph, 1)
for node, dist in sorted(distances.items()):
if dist != math.inf:
print(f"노드 {node}까지 최단 거리: {dist}")
# 출력:
# 노드 1까지 최단 거리: 0
# 노드 2까지 최단 거리: 0
# 노드 3까지 최단 거리: 1
# 노드 4까지 최단 거리: 1
# 노드 5까지 최단 거리: 0
# 노드 6까지 최단 거리: 1
# 노드 7까지 최단 거리: 1
🎮 실전 예제: 미로에서 문 열기
from collections import deque
from typing import List, Tuple
def maze_with_keys(maze: List[List[str]]) -> int:
"""
미로 문제: 0-1 BFS 활용
'.': 통로 (0 비용)
'D': 문 (열려면 0 비용, 닫혀있으면 1 비용)
'#': 벽 (이동 불가)
'S': 시작점
'E': 도착점
"""
rows, cols = len(maze), len(maze[0])
# 시작점과 도착점 찾기
start, end = None, None
for i in range(rows):
for j in range(cols):
if maze[i][j] == 'S':
start = (i, j)
elif maze[i][j] == 'E':
end = (i, j)
# 0-1 BFS
dq = deque([(start[0], start[1], 0)]) # (row, col, keys_used)
visited = {start: 0}
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
while dq:
row, col, keys = dq.popleft()
if (row, col) == end:
return keys
for dr, dc in directions:
new_row, new_col = row + dr, col + dc
new_pos = (new_row, new_col)
if 0 <= new_row < rows and 0 <= new_col < cols:
cell = maze[new_row][new_col]
if cell == '#':
continue
# 문을 열 때 키 사용
new_keys = keys + (1 if cell == 'D' else 0)
# 더 적은 키로 방문 가능한 경우만
if new_pos not in visited or visited[new_pos] > new_keys:
visited[new_pos] = new_keys
if cell == 'D':
dq.append((new_row, new_col, new_keys)) # 뒤에 추가
else:
dq.appendleft((new_row, new_col, new_keys)) # 앞에 추가
return -1
# 사용 예제
maze = [
['S', '.', '.', 'D', '.'],
['.', '#', '.', '#', '.'],
['.', '.', 'D', '.', '.'],
['#', '.', '#', '#', '.'],
['.', '.', '.', '.', 'E']
]
result = maze_with_keys(maze)
print(f"최소 문 열기 횟수: {result}")
# 출력: 최소 문 열기 횟수: 2
🌍 Multi-Source BFS
📍 개념
여러 시작점에서 동시에 BFS를 시작하는 기법입니다.
💻 Python 구현
from collections import deque
from typing import List, Set, Tuple
def multi_source_bfs(grid: List[List[int]], sources: List[Tuple[int, int]]) -> List[List[int]]:
"""
다중 시작점 BFS
Args:
grid: 2D 그리드
sources: 시작점 리스트
Returns:
각 셀에서 가장 가까운 시작점까지의 거리
"""
rows, cols = len(grid), len(grid[0])
distances = [[-1] * cols for _ in range(rows)]
# 모든 시작점을 큐에 추가
queue = deque()
for row, col in sources:
queue.append((row, col, 0))
distances[row][col] = 0
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
while queue:
row, col, dist = queue.popleft()
for dr, dc in directions:
new_row, new_col = row + dr, col + dc
if (0 <= new_row < rows and
0 <= new_col < cols and
distances[new_row][new_col] == -1 and
grid[new_row][new_col] == 0):
distances[new_row][new_col] = dist + 1
queue.append((new_row, new_col, dist + 1))
return distances
# 사용 예제: 병원까지의 거리
grid = [
[0, 0, 0, 0, 0],
[0, 1, 0, 1, 0],
[0, 0, 0, 0, 0],
[0, 1, 0, 1, 0],
[0, 0, 0, 0, 0]
]
# 병원 위치
hospitals = [(0, 0), (0, 4), (4, 0), (4, 4)]
distances = multi_source_bfs(grid, hospitals)
print("각 위치에서 가장 가까운 병원까지의 거리:")
for row in distances:
print(' '.join(f'{d:2d}' if d != -1 else ' #' for d in row))
# 출력:
# 각 위치에서 가장 가까운 병원까지의 거리:
# 0 1 2 1 0
# 1 # 2 # 1
# 2 2 2 2 2
# 1 # 2 # 1
# 0 1 2 1 0
🏥 실전 예제: 역 배치 최적화
def optimize_station_placement(city_grid: List[List[int]],
num_stations: int) -> List[Tuple[int, int]]:
"""
도시에 역을 배치하여 최대 거리를 최소화
"""
rows, cols = len(city_grid), len(city_grid[0])
# 가능한 모든 위치
possible_positions = []
for i in range(rows):
for j in range(cols):
if city_grid[i][j] == 0: # 빈 공간
possible_positions.append((i, j))
# 가장 먼 거리를 최소화하는 역 배치 찾기
# (실제로는 훈리스틱 탐색 등을 사용)
best_stations = []
min_max_distance = float('inf')
# 예시: 균등하게 분포된 위치 선택
step = len(possible_positions) // num_stations
best_stations = [possible_positions[i * step] for i in range(num_stations)]
# Multi-source BFS로 거리 계산
distances = multi_source_bfs(city_grid, best_stations)
return best_stations, distances
# 사용 예제
city = [
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 0, 1, 0, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 0, 1, 0, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 0, 1, 0, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0]
]
stations, distances = optimize_station_placement(city, 4)
print(f"추천 역 위치: {stations}")
🧩 실전 코딩 테스트 문제
이제 실제 코딩 테스트에서 자주 나오는 BFS 문제들을 풀어보겠습니다.
🥇 문제 1: 섬의 개수 (Number of Islands)
📝 문제 설명
2D 그리드가 주어지고, ‘1’은 땅, ‘0’은 물을 나타냅니다. 섬의 개수를 구하세요.
💡 풀이 전략
- 각 ‘땅’ 셀에서 BFS 시작
- 연결된 모든 ‘땅’을 방문 처리
- BFS 실행 횟수 = 섬의 개수
💻 코드
from collections import deque
from typing import List
def numIslands(grid: List[List[str]]) -> int:
"""
LeetCode 200: Number of Islands
난이도: Medium
"""
if not grid or not grid[0]:
return 0
rows, cols = len(grid), len(grid[0])
visited = set()
islands = 0
def bfs(start_row: int, start_col: int):
queue = deque([(start_row, start_col)])
visited.add((start_row, start_col))
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
while queue:
row, col = queue.popleft()
for dr, dc in directions:
new_row, new_col = row + dr, col + dc
if (0 <= new_row < rows and
0 <= new_col < cols and
grid[new_row][new_col] == '1' and
(new_row, new_col) not in visited):
visited.add((new_row, new_col))
queue.append((new_row, new_col))
# 모든 셀 탐색
for i in range(rows):
for j in range(cols):
if grid[i][j] == '1' and (i, j) not in visited:
bfs(i, j)
islands += 1
return islands
# 테스트
grid1 = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
print(f"섬의 개수: {numIslands(grid1)}") # 출력: 1
grid2 = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
print(f"섬의 개수: {numIslands(grid2)}") # 출력: 3
🥈 문제 2: 오렌지 썽기 (Rotting Oranges)
📝 문제 설명
그리드에서:
- 0: 빈 셀
- 1: 신선한 오렌지
- 2: 썸은 오렌지
매분 썸은 오렌지의 4방향 인접 셀의 신선한 오렌지가 썽습니다. 모든 오렌지가 썽는 데 걸리는 최소 시간을 반환하세요.
💡 풀이 전략
- 모든 썸은 오렌지를 큐에 추가 (Multi-source BFS)
- BFS로 레벨별로 탐색
- 각 레벨 = 1분
💻 코드
from collections import deque
from typing import List
def orangesRotting(grid: List[List[int]]) -> int:
"""
LeetCode 994: Rotting Oranges
난이도: Medium
"""
rows, cols = len(grid), len(grid[0])
queue = deque()
fresh_count = 0
# 초기 상태 파악
for i in range(rows):
for j in range(cols):
if grid[i][j] == 2:
queue.append((i, j, 0)) # (row, col, time)
elif grid[i][j] == 1:
fresh_count += 1
# 신선한 오렌지가 없으면 0 반환
if fresh_count == 0:
return 0
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
max_time = 0
# Multi-source BFS
while queue:
row, col, time = queue.popleft()
max_time = max(max_time, time)
for dr, dc in directions:
new_row, new_col = row + dr, col + dc
if (0 <= new_row < rows and
0 <= new_col < cols and
grid[new_row][new_col] == 1):
# 신선한 오렌지를 썸은 오렌지로 변경
grid[new_row][new_col] = 2
fresh_count -= 1
queue.append((new_row, new_col, time + 1))
# 남은 신선한 오렌지가 있으면 -1
return max_time if fresh_count == 0 else -1
# 테스트
grid1 = [
[2,1,1],
[1,1,0],
[0,1,1]
]
print(f"최소 시간: {orangesRotting(grid1)}분") # 출력: 4
grid2 = [
[2,1,1],
[0,1,1],
[1,0,1]
]
print(f"최소 시간: {orangesRotting(grid2)}분") # 출력: -1
grid3 = [[0,2]]
print(f"최소 시간: {orangesRotting(grid3)}분") # 출력: 0
🥉 문제 3: 이진 행렬의 최단 경로 (Shortest Path in Binary Matrix)
📝 문제 설명
N x N 이진 행렬에서 (0,0)부터 (N-1,N-1)까지의 최단 경로를 찾으세요. 0은 비어있는 셀이고 1은 장애물입니다. 8방향 이동 가능합니다.
💡 풀이 전략
- BFS로 최단 경로 찾기
- 8방향 이동 (대각선 포함)
- 시작점과 도착점이 0인지 확인
💻 코드
from collections import deque
from typing import List
def shortestPathBinaryMatrix(grid: List[List[int]]) -> int:
"""
LeetCode 1091: Shortest Path in Binary Matrix
난이도: Medium
"""
n = len(grid)
# 시작점이나 도착점이 막힌 경우
if grid[0][0] == 1 or grid[n-1][n-1] == 1:
return -1
# 한 칸짜리 그리드
if n == 1:
return 1
# 8방향 이동
directions = [
(0, 1), (1, 0), (0, -1), (-1, 0), # 4방향
(1, 1), (1, -1), (-1, 1), (-1, -1) # 대각선
]
queue = deque([(0, 0, 1)]) # (row, col, path_length)
visited = {(0, 0)}
while queue:
row, col, length = queue.popleft()
# 도착점 도달
if row == n - 1 and col == n - 1:
return length
# 8방향 탐색
for dr, dc in directions:
new_row, new_col = row + dr, col + dc
if (0 <= new_row < n and
0 <= new_col < n and
grid[new_row][new_col] == 0 and
(new_row, new_col) not in visited):
visited.add((new_row, new_col))
queue.append((new_row, new_col, length + 1))
return -1 # 경로 없음
# 테스트
grid1 = [
[0,1],
[1,0]
]
print(f"최단 경로 길이: {shortestPathBinaryMatrix(grid1)}") # 출력: 2
grid2 = [
[0,0,0],
[1,1,0],
[1,1,0]
]
print(f"최단 경로 길이: {shortestPathBinaryMatrix(grid2)}") # 출력: 4
grid3 = [
[1,0,0],
[1,1,0],
[1,1,0]
]
print(f"최단 경로 길이: {shortestPathBinaryMatrix(grid3)}") # 출력: -1
## 🏆 문제 4: 단어 사다리 (Word Ladder)
### 📝 문제 설명
시작 단어에서 한 번에 한 글자씩 바꿔 목표 단어로 변환하는 최단 수열 길이를 구하세요. 단어 리스트에 있는 단어만 사용 가능합니다.
### 💡 풀이 전략
1. 각 단어를 그래프의 노드로 취급
2. 한 글자만 다른 단어 = 간선
3. BFS로 최단 경로 찾기
### 💻 코드
from collections import deque
from typing import List
def ladderLength(beginWord: str, endWord: str, wordList: List[str]) -> int:
“””
LeetCode 127: Word Ladder
난이도: Hard
“””
word_set = set(wordList)
if endWord not in word_set:
return 0
queue = deque([(beginWord, 1)]) # (word, length)
visited = {beginWord}
while queue:
word, length = queue.popleft()
# 목표 단어 도달
if word == endWord:
return length
# 한 글자씩 바꿔보기
for i in range(len(word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
next_word = word\[:i\] + c + word\[i+1:\]
if next_word in word_set and next_word not in visited:
visited.add(next_word)
queue.append((next_word, length + 1))
return 0 # 변환 불가
테스트
beginWord = “hit”
endWord = “cog”
wordList = [“hot”,”dot”,”dog”,”lot”,”log”,”cog”]
result = ladderLength(beginWord, endWord, wordList)
print(f”최단 변환 수열 길이: {result}”)
출력: 5
설명: hit -> hot -> dot -> dog -> cog
wordList2 = [“hot”,”dot”,”dog”,”lot”,”log”]
result2 = ladderLength(beginWord, endWord, wordList2)
print(f”최단 변환 수열 길이: {result2}”)
출력: 0 (cog가 wordList에 없음)
## 🏅 문제 5: 백준 2178 - 미로 탐색
### 📝 문제 설명
N×M크기의 배열로 표현되는 미로가 있다. 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타냅니다. (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오.
### 💡 풀이 전략
1. BFS로 최단 경로 찾기
2. 시작 칸도 포함하여 카운트
3. 상하좌우 4방향 이동
### 💻 코드
from collections import deque
from typing import List
def solve_baekjoon_2178():
“””
백준 2178: 미로 탐색
난이도: Silver 1
“””
# 입력 받기
n, m = map(int, input().split())
maze = \[\]
for _ in range(n):
row = input().strip()
maze.append(\[int(c) for c in row\])
# BFS
queue = deque(\[(0, 0, 1)\]) # (row, col, distance)
visited = \[\[False\] \* m for _ in range(n)\]
visited\[0\]\[0\] = True
directions = \[(0, 1), (1, 0), (0, -1), (-1, 0)\]
while queue:
row, col, dist = queue.popleft()
# 도착점 도달
if row == n - 1 and col == m - 1:
return dist
# 4방향 탐색
for dr, dc in directions:
new_row, new_col = row + dr, col + dc
if (0 \<= new_row \< n and
0 \<= new_col \< m and
maze\[new_row\]\[new_col\] == 1 and
not visited\[new_row\]\[new_col\]):
visited\[new_row\]\[new_col\] = True
queue.append((new_row, new_col, dist + 1))
return -1
테스트 함수 (실제 제출시에는 사용 안 함)
def test_maze():
# 예제 입력
# 4 6
# 101111
# 101010
# 101011
# 111011
maze = \[
\[1,0,1,1,1,1\],
\[1,0,1,0,1,0\],
\[1,0,1,0,1,1\],
\[1,1,1,0,1,1\]
\]
n, m = 4, 6
queue = deque(\[(0, 0, 1)\])
visited = \[\[False\] \* m for _ in range(n)\]
visited\[0\]\[0\] = True
directions = \[(0, 1), (1, 0), (0, -1), (-1, 0)\]
while queue:
row, col, dist = queue.popleft()
if row == n - 1 and col == m - 1:
print(f"최단 경로: \{dist\}")
return dist
for dr, dc in directions:
new_row, new_col = row + dr, col + dc
if (0 \<= new_row \< n and
0 \<= new_col \< m and
maze\[new_row\]\[new_col\] == 1 and
not visited\[new_row\]\[new_col\]):
visited\[new_row\]\[new_col\] = True
queue.append((new_row, new_col, dist + 1)) test_maze() # 출력: 15
## 💪 문제 6: 프로그래머스 - 타겟 넘버
### 📝 문제 설명
n개의 음이 아닌 정수들이 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 타겟 넘버를 만드는 방법의 수를 구하라.
### 💡 풀이 전략
1. DFS나 BFS 모두 가능하지만 BFS로 풀 수 있음
2. 각 숫자를 더하거나 빼는 2가지 선택
3. 모든 숫자를 사용한 후 타겟과 같은지 확인
### 💻 코드
from collections import deque
from typing import List
def solution(numbers: List[int], target: int) -> int:
“””
프로그래머스: 타겟 넘버
Level 2
“””
queue = deque([(0, 0)]) # (index, current_sum)
count = 0
while queue:
index, current_sum = queue.popleft()
# 모든 숫자를 사용한 경우
if index == len(numbers):
if current_sum == target:
count += 1
else:
# 더하기
queue.append((index + 1, current_sum + numbers\[index\]))
# 빼기
queue.append((index + 1, current_sum - numbers\[index\]))
return count
테스트
numbers = [1, 1, 1, 1, 1]
target = 3
print(f”타겟 넘버를 만드는 방법: {solution(numbers, target)}개”)
출력: 5
설명: -1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
numbers2 = [4, 1, 2, 1]
target2 = 4
print(f”타겟 넘버를 만드는 방법: {solution(numbers2, target2)}개”)
출력: 2
설명: +4+1-2+1 = 4
+4-1+2-1 = 4
## 🥇 문제 7: 프로그래머스 - 네트워크
### 📝 문제 설명
네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return하도록 solution 함수를 작성하시오.
### 💡 풀이 전략
1. 각 컴퓨터에서 BFS 실행
2. 연결된 모든 컴퓨터를 방문 처리
3. BFS 실행 횟수 = 네트워크 개수
### 💻 코드
from collections import deque
from typing import List
def solution(n: int, computers: List[List[int]]) -> int:
“””
프로그래머스: 네트워크
Level 3
“””
def bfs(start: int):
queue = deque([start])
visited[start] = True
while queue:
node = queue.popleft()
for neighbor in range(n):
# 연결되어 있고 방문하지 않았으면
if computers\[node\]\[neighbor\] == 1 and not visited\[neighbor\]:
visited\[neighbor\] = True
queue.append(neighbor)
visited = \[False\] \* n
networks = 0
for i in range(n):
if not visited\[i\]:
bfs(i)
networks += 1
return networks
테스트
computers1 = [
[1, 1, 0],
[1, 1, 0],
[0, 0, 1]
]
print(f”네트워크 개수: {solution(3, computers1)}”)
출력: 2
computers2 = [
[1, 1, 0],
[1, 1, 1],
[0, 1, 1]
]
print(f”네트워크 개수: {solution(3, computers2)}”)
출력: 1
## 🎉 문제 8: 백준 7576 - 토마토
### 📝 문제 설명
토마토가 보관되는 창고에 보관되는 토마토들 중에는 잍은 것도 있지만, 아직 잍지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 잍은 토마토들의 인접한 곳에 있는 잍지 않은 토마토들은 잍은 토마토의 영향을 받아 잍게 된다. 토마토가 모두 잍을 때까지의 최소 날짜를 구하라.
### 💡 풀이 전략
1. 모든 잍은 토마토를 큐에 추가 (Multi-source BFS)
2. 레벨별로 BFS 실행
3. 각 레벨 = 1일
### 💻 코드
from collections import deque
from typing import List
def solve_tomato():
“””
백준 7576: 토마토
난이도: Gold 5
“””
# 입력
m, n = map(int, input().split())
grid = \[\]
for _ in range(n):
grid.append(list(map(int, input().split())))
# 초기 설정
queue = deque()
unripe_count = 0
for i in range(n):
for j in range(m):
if grid\[i\]\[j\] == 1: # 잍은 토마토
queue.append((i, j, 0)) # (row, col, day)
elif grid\[i\]\[j\] == 0: # 안 잍은 토마토
unripe_count += 1
# 모두 잍은 상태
if unripe_count == 0:
return 0
directions = \[(0, 1), (1, 0), (0, -1), (-1, 0)\]
max_day = 0
# Multi-source BFS
while queue:
row, col, day = queue.popleft()
max_day = max(max_day, day)
for dr, dc in directions:
new_row, new_col = row + dr, col + dc
if (0 \<= new_row \< n and
0 \<= new_col \< m and
grid\[new_row\]\[new_col\] == 0):
grid\[new_row\]\[new_col\] = 1
unripe_count -= 1
queue.append((new_row, new_col, day + 1))
# 안 잍은 토마토가 남아있으면 -1
return max_day if unripe_count == 0 else -1
테스트 함수
def test_tomato():
# 예제 1
grid1 = \[
\[0, 0, 0, 0, 0, 0\],
\[0, 0, 0, 0, 0, 0\],
\[0, 0, 0, 0, 0, 0\],
\[0, 0, 0, 0, 0, 1\]
\]
# 정답: 8
# 예제 2
grid2 = \[
\[0, -1, 0, 0, 0, 0\],
\[-1, 0, 0, 0, 0, 0\],
\[0, 0, 0, 0, 0, 0\],
\[0, 0, 0, 0, 0, 1\]
\]
# 정답: -1
# 예제 3
grid3 = \[
\[1, -1, 0, 0, 0, 0\],
\[0, -1, 0, 0, 0, 0\],
\[0, 0, 0, 0, -1, 0\],
\[0, 0, 0, 0, -1, 1\]
\]
# 정답: 6
print("테스트는 실제 백준에 제출하여 확인하세요.") test_tomato()
## 🎯 문제 9: 백준 7569 - 토마토 (3D)
### 📝 문제 설명
위 토마토 문제의 3차원 버전입니다. 토마토가 여러 층에 쌓여있습니다.
### 💡 풀이 전략
1. 3D BFS (위, 아래 방향 추가)
2. 6방향 이동 (상하좌우 + 위아래)
3. Multi-source BFS
### 💻 코드
from collections import deque
from typing import List
def solve_tomato_3d():
“””
백준 7569: 토마토 (3D)
난이도: Gold 5
“””
# 입력: M(x), N(y), H(z)
m, n, h = map(int, input().split())
grid = \[\]
for _ in range(h):
layer = \[\]
for _ in range(n):
layer.append(list(map(int, input().split())))
grid.append(layer)
# 초기 설정
queue = deque()
unripe_count = 0
for z in range(h):
for y in range(n):
for x in range(m):
if grid\[z\]\[y\]\[x\] == 1: # 잍은 토마토
queue.append((z, y, x, 0)) # (z, y, x, day)
elif grid\[z\]\[y\]\[x\] == 0: # 안 잍은 토마토
unripe_count += 1
if unripe_count == 0:
return 0
# 6방향 이동 (좌, 우, 전, 후, 상, 하)
directions = \[
(0, 0, 1), (0, 0, -1), # x축
(0, 1, 0), (0, -1, 0), # y축
(1, 0, 0), (-1, 0, 0) # z축
\]
max_day = 0
while queue:
z, y, x, day = queue.popleft()
max_day = max(max_day, day)
for dz, dy, dx in directions:
nz, ny, nx = z + dz, y + dy, x + dx
if (0 \<= nz \< h and
0 \<= ny \< n and
0 \<= nx \< m and
grid\[nz\]\[ny\]\[nx\] == 0):
grid\[nz\]\[ny\]\[nx\] = 1
unripe_count -= 1
queue.append((nz, ny, nx, day + 1))
return max_day if unripe_count == 0 else -1 print("실제 백준에 제출하여 테스트하세요.")
## 🏆 문제 10: 백준 1697 - 숨바꼭질
### 📝 문제 설명
수빈이 동생과 숨바꼭질을 하고 있다. 수빈은 현재 점 N에 있고, 동생은 점 K에 있다. 수빈이 있는 위치가 X일 때 걸어가면 1초 후에 X-1 또는 X+1로 이동하게 되고, 순간이동을 하면 1초 후에 2*X의 위치로 이동하게 된다. 수빈이 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하라.
### 💡 풀이 전략
1. BFS로 최단 시간 찾기
2. 3가지 이동 방법: X-1, X+1, 2*X
3. 범위: 0 ≤ X ≤ 100,000
### 💻 코드
from collections import deque
def solve_hide_and_seek():
“””
백준 1697: 숨바꼭질
난이도: Silver 1
“””
n, k = map(int, input().split())
if n == k:
return 0
MAX = 100000
visited = [False] * (MAX + 1)
queue = deque([(n, 0)]) # (position, time)
visited[n] = True
while queue:
pos, time = queue.popleft()
# 3가지 이동 방법
next_positions = \[pos - 1, pos + 1, pos \* 2\]
for next_pos in next_positions:
if next_pos == k:
return time + 1
if 0 \<= next_pos \<= MAX and not visited\[next_pos\]:
visited\[next_pos\] = True
queue.append((next_pos, time + 1))
return -1
테스트
def test_hide_and_seek():
test_cases = [
(5, 17, 4), # 5 -> 10 -> 9 -> 18 -> 17
(0, 0, 0), # 이미 같은 위치
(1, 100000, 16),
]
for n, k, expected in test_cases:
# BFS 구현
MAX = 100000
visited = \[False\] \* (MAX + 1)
queue = deque(\[(n, 0)\])
visited\[n\] = True
result = 0
if n == k:
result = 0
else:
while queue:
pos, time = queue.popleft()
next_positions = \[pos - 1, pos + 1, pos \* 2\]
for next_pos in next_positions:
if next_pos == k:
result = time + 1
queue.clear()
break
if 0 \<= next_pos \<= MAX and not visited\[next_pos\]:
visited\[next_pos\] = True
queue.append((next_pos, time + 1))
print(f"N=\{n\}, K=\{k\}: 최단 시간 = \{result\}초 (예상: \{expected\}초)") test_hide_and_seek()
---
# ⚠️ 트러블슈팅
BFS 구현 시 자주 발생하는 오류와 해결 방법을 알아보겠습니다.
## 🚫 오류 1: 방문 체크를 큐 삽입 전에 하지 않음
### ❌ 잘못된 코드
from collections import deque
def bfs_wrong(graph, start):
queue = deque([start])
visited = set()
while queue:
node = queue.popleft()
# 여기서 방문 체크 - 너무 늦음!
if node in visited:
continue
visited.add(node)
for neighbor in graph\[node\]:
queue.append(neighbor) # 중복 추가 가능!
### ✅ 올바른 코드
from collections import deque
def bfs_correct(graph, start):
queue = deque([start])
visited = {start} # 시작점 방문 처리
while queue:
node = queue.popleft()
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor) # 큐 삽입 전에 방문 처리!
queue.append(neighbor)
### 💡 설명
큐에 넣기 **전**에 방문 처리해야 중복 방문을 방지할 수 있습니다. 그렇지 않으면 같은 노드가 큐에 여러 번 들어가 시간 복잡도가 급격히 증가합니다.
## 🚫 오류 2: 레벨 별 처리를 잘못 구현
### ❌ 잘못된 코드
def bfs_level_wrong(root):
queue = deque([root])
result = []
while queue:
# 현재 큐 크기를 사용하지 않음
node = queue.popleft()
result.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
# 레벨 구분이 안 됨!
return result
### ✅ 올바른 코드
def bfs_level_correct(root):
if not root:
return []
queue = deque([root])
result = []
while queue:
level = []
level_size = len(queue) # 현재 레벨의 노드 수
# 현재 레벨의 모든 노드 처리
for _ in range(level_size):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)
return result
### 💡 설명
레벨별 처리가 필요한 경우 `len(queue)`를 저장해두고 해당 횟수만큼만 처리해야 합니다.
## 🚫 오류 3: 그리드 바운드리 체크 누락
### ❌ 잘못된 코드
def bfs_grid_wrong(grid, start):
queue = deque([start])
visited = {start}
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
while queue:
row, col = queue.popleft()
for dr, dc in directions:
new_row, new_col = row + dr, col + dc
# 바운드리 체크 누락!
if grid\[new_row\]\[new_col\] == 0: # IndexError 발생 가능
queue.append((new_row, new_col))
### ✅ 올바른 코드
def bfs_grid_correct(grid, start):
rows, cols = len(grid), len(grid[0])
queue = deque([start])
visited = {start}
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
while queue:
row, col = queue.popleft()
for dr, dc in directions:
new_row, new_col = row + dr, col + dc
# 바운드리 체크 먼저!
if (0 \<= new_row \< rows and
0 \<= new_col \< cols and
(new_row, new_col) not in visited and
grid\[new_row\]\[new_col\] == 0):
visited.add((new_row, new_col))
queue.append((new_row, new_col))
### 💡 설명
그리드 탐색 시 항상 배열 바운드리를 먼저 체크해야 `IndexError`를 방지할 수 있습니다.
## 🚫 오류 4: 시작점 방문 처리 누락
### ❌ 잘못된 코드
def bfs_start_wrong(graph, start):
queue = deque([start])
visited = set() # start를 visited에 추가하지 않음!
while queue:
node = queue.popleft()
if node in visited:
continue
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
queue.append(neighbor)
# 시작점이 다시 방문될 수 있음!
### ✅ 올바른 코드
def bfs_start_correct(graph, start):
queue = deque([start])
visited = {start} # 시작점 방문 처리!
while queue:
node = queue.popleft()
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
## 🚫 오류 5: 최단 경로에서 경로를 제대로 추적하지 않음
### ❌ 잘못된 코드
def bfs_path_wrong(graph, start, goal):
queue = deque([(start, [start])])
visited = {start}
while queue:
node, path = queue.popleft()
if node == goal:
return path
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
# 경로를 복사하지 않고 직접 수정!
path.append(neighbor)
queue.append((neighbor, path)) # 문제!
### ✅ 올바른 코드
def bfs_path_correct(graph, start, goal):
queue = deque([(start, [start])])
visited = {start}
while queue:
node, path = queue.popleft()
if node == goal:
return path
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
# 새 리스트 생성!
new_path = path + \[neighbor\]
queue.append((neighbor, new_path))
### 💡 설명
경로를 추적할 때는 항상 **새로운 리스트를 생성**해야 합니다. 그렇지 않으면 모든 경로가 같은 리스트를 공유하게 됩니다.
## 🚫 오류 6: 미로에서 시작점이나 도착점이 벽인 경우 처리 안 함
### ❌ 잘못된 코드
def bfs_maze_wrong(maze, start, end):
# 시작점이나 도착점이 벽인지 확인 안 함!
queue = deque(\[start\])
visited = \{start\}
while queue:
pos = queue.popleft()
if pos == end:
return True
# ...
return False
### ✅ 올바른 코드
def bfs_maze_correct(maze, start, end):
# 시작점이나 도착점이 벽인 경우 처리
if maze\[start\[0\]\]\[start\[1\]\] == 1 or maze\[end\[0\]\]\[end\[1\]\] == 1:
return False
queue = deque(\[start\])
visited = \{start\}
while queue:
pos = queue.popleft()
if pos == end:
return True
# ...
return False
## ✅ BFS 체크리스트
BFS 구현 시 확인 사항
☐ 큐를 사용하는가? (deque)
☐ 시작점을 visited에 추가했는가?
☐ 큐에 넣기 전에 visited 체크하는가?
☐ 그리드인 경우 바운드리 체크를 하는가?
☐ 레벨별 처리가 필요한 경우 len(queue)를 저장했는가?
☐ 경로를 추적하는 경우 새 리스트를 생성하는가?
☐ 시작점과 도착점이 유효한지 확인했는가?
☐ 방향 벡터가 올바른가? (예: 4방향, 8방향)
☐ 종료 조건을 올바르게 처리하는가?
☐ 모든 엣지 케이스를 처리했는가? (빈 그래프, 노드 하나 등)
## 📊 성능 최적화 팁
### 1. 적절한 자료구조 사용
❌ 느림 - list로 visited 관리
visited = []
if node not in visited: # O(n) 검색
visited.append(node)
✅ 빠름 - set으로 visited 관리
visited = set()
if node not in visited: # O(1) 검색
visited.add(node)
### 2. 불필요한 복사 피하기
❌ 메모리 낭비
queue.append((node, path[:])) # 리스트 복사
✅ parent 딕셔너리로 경로 추적
parent[neighbor] = node
나중에 경로 재구성
### 3. 조기 종료
✅ 목표 발견 시 즉시 반환
if neighbor == goal:
return construct_path(…)
queue.append(neighbor)
---
# 📚 참고 자료
## 🌐 온라인 리소스
### 📚 튜토리얼
- [GeeksforGeeks - BFS for a Graph](
graph TD
A[“🔵 기초: BFS 개념”] –> B[“🟢 초급: 기본 구현”]
B –> C[“🟡 중급: 실전 문제”]
C –> D[“🟠 고급: 최적화 기법”]
D –> E[“🔴 마스터: 복잡한 문제”]
style A fill:#e1f5ff
style B fill:#c3f0ca
style C fill:#fff4c3
style D fill:#ffe8c3
style E fill:#ffc3c3
```
✨ 핵심 요약
- BFS는 레벨별로 탐색 - 큐 사용
- 최단 경로를 보장 - 가중치 없는 그래프에서
- 시간 복잡도 O(V + E) - 효율적
- 방문 처리는 큐 삽입 전 - 중복 방지
- 다양한 응용 - 게임, 네트워크, AI 등
🚀 다음 단계
- 💪 연습하기: LeetCode에서 50개 문제 풀기
- 🎯 프로젝트: Unity로 길찾기 AI 구현
- 📚 심화 학습: A* 알고리즘 학습
- 🔍 변형 연구: Dijkstra, Bellman-Ford 학습
💬 피드백
이 가이드가 도움이 되었나요? 피드백이나 추가 요청사항은 언제든지 환영합니다!
행운을 빌어요! 행복한 코딩 되세요! 🚀✨
이 문서는 2026년 1월 15일에 작성되었습니다.