BFS / DFS
자료구조 토픽(ds-07)에서는 그래프의 구조와 인접 행렬·인접 리스트 표현, BFS·DFS 각각의 동작을 따로 살펴봤다면, 여기서는 완전히 같은 그래프를 BFS와 DFS로 동시에 탐색했을 때 방문 순서가 왜, 어떻게 달라지는지를 비교합니다. 핵심은 딱 하나 — 큐(Queue)를 쓰느냐, 스택(Stack)을 쓰느냐입니다.
핵심 개념
BFS — 큐(FIFO) 기반
먼저 발견한 노드를 먼저 방문합니다(First In First Out). 그래서 시작 노드와 가까운 노드부터 한 단계씩, 층(레벨) 단위로 넓게 퍼지며 탐색합니다.
핵심 개념
DFS — 스택(LIFO) 기반
가장 나중에 발견한 노드를 먼저 방문합니다(Last In First Out). 그래서 한 갈래를 끝까지 깊게 파고든 뒤에야 다른 갈래로 되돌아갑니다(백트래킹).
핵심 개념
같은 그래프, 다른 순서
그래프와 시작 노드가 완전히 같아도, 방문 대기열을 큐로 관리하는지 스택으로 관리하는지에 따라 두 번째 노드부터 방문 순서가 갈라지기 시작합니다.
핵심 개념
시간복잡도는 동일
BFS와 DFS 모두 모든 노드와 간선을 한 번씩만 확인하므로 시간복잡도는 인접 리스트 기준 O(V+E)로 같습니다. 차이는 속도가 아니라 "방문 순서"에 있습니다.
핵심 개념
언제 BFS를 쓰는가
시작 노드로부터 "가장 가까운" 경로나 최단 거리를 찾을 때 유리합니다. 층 단위로 퍼지기 때문에 간선 수 기준으로는 처음 도착한 경로가 곧 최단 경로입니다(간선마다 가중치가 다르면 해당하지 않습니다).
핵심 개념
언제 DFS를 쓰는가
한 갈래를 끝까지 따라가 봐야 하는 경우(백트래킹, 미로 탐색, 위상 정렬 등)에 유리합니다. 재귀 호출도 결국 함수 호출 스택을 쓰는 것이라 DFS와 원리가 같습니다.
무엇이 같고 무엇이 다른가
BFS와 DFS는 그래프의 모든 노드를 빠짐없이 한 번씩 방문하는 기본 탐색입니다. 다음에 방문할 노드를 큐에서 꺼내면 BFS, 스택에서 꺼내면 DFS가 되고, 이 차이 하나가 최단 거리 탐색에 유리한지 깊은 구조 탐색에 유리한지를 가릅니다.
숫자로 확인하기
자주 하는 오해
면접에서 이렇게 물어요
면접 질문
BFS와 DFS는 언제 각각 쓰나요?
간선 수 기준의 최단 거리나 가까운 노드부터 처리해야 하면 BFS를 씁니다. 경로를 끝까지 따라가야 하는 문제, 사이클 탐지, 위상 정렬(사이클 없는 방향 그래프에서), 모든 경우를 훑는 백트래킹은 DFS 구조를 씁니다.
면접 질문
시간 복잡도는 어떻게 되나요?
인접 리스트로 표현하면 O(V + E)입니다. 인접 행렬은 한 노드의 이웃을 찾는 데 O(V)가 들어서 전체 O(V²)입니다.
면접 질문
재귀 DFS의 단점은 무엇인가요?
그래프가 아주 깊으면 호출 스택이 넘쳐 스택 오버플로가 날 수 있습니다. 이럴 때는 명시적 스택으로 바꾸거나 언어의 재귀 깊이 제한을 확인합니다.
면접 질문
BFS로 미로의 최단 경로를 어떻게 구하나요?
시작 칸을 큐에 넣고 층별로 퍼져 나가며 각 칸에 도달한 거리(또는 이전 칸)를 기록합니다. 도착 칸에 처음 닿은 시점의 거리가 간선 수 기준 최단 거리입니다.
실제 시스템에서는
Files.walkFileTree의 문서는 파일 트리를 깊이 우선으로 순회한다고 설명합니다(같은 디렉터리 안의 방문 순서는 가정할 수 없습니다).
StackOverflowError를 일으키고, 파이썬은 sys.setrecursionlimit로 재귀 깊이 제한을 조절할 수 있지만 너무 높이면 프로세스가 비정상 종료할 수 있습니다. 깊은 그래프를 재귀 DFS로 풀 때는 이 한계를 먼저 확인해야 합니다.
함께 보면 좋은 토픽
참고 자료
Java — BFS (너비 우선 탐색, 큐)
/* ── 큐(Queue): 먼저 들어온 노드를 먼저 꺼냄(FIFO) ─────────── */ public List<Integer> bfs(int start, List<List<Integer>> adj) { List<Integer> order = new ArrayList<>(); boolean[] visited = new boolean[adj.size()]; Queue<Integer> queue = new LinkedList<>(); queue.offer(start); visited[start] = true; while (!queue.isEmpty()) { int cur = queue.poll(); // 큐의 맨 앞에서 꺼냄 order.add(cur); for (int next : adj.get(cur)) { if (!visited[next]) { visited[next] = true; // 발견 즉시 방문 표시(중복 방지) queue.offer(next); // 큐의 맨 뒤에 추가 } } } return order; }
queue.poll()은 항상 가장 먼저 들어온(=시작 노드에서 가장 가까운) 노드를 꺼내기 때문에, 방문 순서가 자연스럽게 "가까운 노드부터" 층 단위로 퍼집니다.
방문 표시를 queue.offer() 시점(발견 즉시)에 하는 것이 핵심입니다 — 방문 시점에 표시하면 같은 노드가 큐에 중복으로 쌓일 수 있습니다.
Java — DFS (깊이 우선 탐색, 스택)
/* ── 스택(Stack): 가장 나중에 들어온 노드를 먼저 꺼냄(LIFO) ── */ public List<Integer> dfs(int start, List<List<Integer>> adj) { List<Integer> order = new ArrayList<>(); boolean[] visited = new boolean[adj.size()]; Deque<Integer> stack = new ArrayDeque<>(); stack.push(start); while (!stack.isEmpty()) { int cur = stack.pop(); // 스택의 맨 위(가장 최근)에서 꺼냄 if (visited[cur]) continue; // 중복으로 쌓였던 노드는 건너뜀 visited[cur] = true; order.add(cur); for (int next : adj.get(cur)) { if (!visited[next]) stack.push(next); } } return order; }
BFS 코드와 비교해보면 Queue가 Deque(스택)으로, poll()이 pop()으로 바뀐 것 외에는 구조가 거의 동일합니다.
방문 표시를 pop() 시점(꺼낼 때)으로 옮긴 이유는, 스택은 같은 노드가 여러 경로로 중복 push될 수 있어 꺼낼 때 한 번 더 확인이 필요하기 때문입니다.
Java — DFS (재귀 버전, 스택과 동일한 원리)
/* ── 재귀 호출도 결국 시스템이 관리하는 스택을 사용함 ─────── */ public void dfsRecursive(int cur, boolean[] visited, List<List<Integer>> adj, List<Integer> order) { visited[cur] = true; order.add(cur); for (int next : adj.get(cur)) { if (!visited[next]) { dfsRecursive(next, visited, adj, order); // 한 갈래를 끝까지 파고든 뒤 되돌아옴 } } }
반복문 + 명시적 스택 버전과 방문 순서가 완전히 같습니다 — dfsRecursive가 자신을 호출할 때마다 함수 호출 스택에 쌓이고,
더 갈 곳이 없으면 스택에서 빠져나오며(return) 이전 갈래로 되돌아가기 때문입니다.
ds-10(동적 프로그래밍)에서 다룬 재귀와 마찬가지로, 그래프에 사이클이 있다면 반드시 visited 체크가 있어야 무한 재귀에 빠지지 않습니다.
Q1
BFS와 DFS 중 큐(Queue)를 사용하는 탐색은?
Q2
최단 경로(간선 가중치가 동일한 그래프)를 찾을 때 더 적합한 탐색은?
Q3
DFS가 스택(또는 재귀)을 사용하는 이유는?