한양과기고 에듀테크 수업도구 대시보드

그래프 탐색 — BFS와 DFS

그래프는 노드(정점) 와 이를 잇는 간선 의 모임입니다. 한 노드에서 출발해 연결된 모든 노드를 빠짐없이 방문하는 방법이 탐색(traversal) 이고, 대표적으로 두 가지가 있습니다. BFS(너비 우선)는 큐(Queue) 로 가까운 곳부터 물결처럼 퍼지고, DFS(깊이 우선)는 스택(Stack) 으로 한 길을 끝까지 파고듭니다. 아래에서 직접 돌려 보고, 노드를 드래그해 그래프 모양도 바꿔 보세요.

탐색 시뮬레이터

속도 620㎳

큐 (Queue) — FIFO

앞에서 꺼내고 · 뒤로 넣는다

방문 순서

시작 노드 A 에서 출발합니다. ▶ 한 단계 를 눌러 진행하세요.

자료구조에 담김(frontier) 지금 처리 중 방문 완료 · 노드를 드래그하면 위치를 바꿀 수 있어요.

BFS vs DFS 한눈에

BFS · 너비 우선

자료구조: 큐 (먼저 들어온 게 먼저 나감)
출발점에서 가까운 노드부터 층층이 방문
가중치 없는 그래프의 최단 경로(간선 수 최소)를 보장
미로 최단 탈출, 친구 관계 n촌 찾기, 웹 크롤링

DFS · 깊이 우선

자료구조: 스택 (재귀 호출로도 구현)
한 갈래를 끝까지 판 뒤 막히면 되돌아옴(백트래킹)
최단 경로는 보장 못 함, 대신 메모리를 덜 씀
미로 생성, 사이클 검출, 위상 정렬, 연결 요소 세기

항목	BFS	DFS
보조 자료구조	`Queue`	`Stack` / 재귀
시간 복잡도	`O(V + E)` — 정점 V, 간선 E 를 한 번씩
공간 복잡도	`O(V)` (한 층이 넓으면 큼)	`O(h)` (가장 깊은 경로 길이)
최단 경로	보장 (무가중치)	보장 안 함

파이썬 의사 코드

# 그래프는 인접 리스트로 표현: graph[u] = [연결된 노드들] from collections import deque def bfs(graph, start): visited = {start} q = deque([start]) while q: u = q.popleft() # 큐: 앞에서 꺼냄 print(u) for v in graph[u]: if v not in visited: visited.add(v) q.append(v) # 뒤로 넣음 def dfs(graph, start, visited=None): if visited is None: visited = set() visited.add(start) print(start) for v in graph[start]: if v not in visited: dfs(graph, v, visited) # 재귀 = 호출 스택이 곧 스택

학습용 인터랙티브 페이지 · 한양과학기술고등학교 프로젝트 허브