그래프 탐색의 두 가지 핵심 알고리즘인 DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)을 개념, 동작 원리, Java 구현, 그리고 문제 유형별 선택 기준까지 정리해볼려 한다.
1. 그래프 표현 방법
그래프 탐색을 구현하기 전에, 그래프를 코드로 어떻게 표현하는지 먼저 알아야 한다.
1-1. 인접 행렬 (Adjacent Matrix)
2차원 배열을 사용하여 간선의 존재 여부를 표현한다.
if (간선 (i, j)가 그래프에 존재) → M[i][j] = 1
그렇지 않으면 → M[i][j] = 0예를 들어 정점 4개(0~3)를 가진 무방향 그래프라면:
0 1 2 3
0 [ 0, 1, 1, 1 ]
1 [ 1, 0, 1, 0 ]
2 [ 1, 1, 0, 1 ]
3 [ 1, 0, 1, 0 ]- 장점: 간선 존재 여부를
O(1)로 확인 가능 - 단점: 정점 수가 많으면 메모리 낭비 (
O(V²))
1-2. 인접 리스트 (Adjacency List)
각 정점에 인접한 정점들을 연결 리스트(또는 ArrayList)로 표현합니다.
0 → [1, 2, 3]
1 → [0, 2]
2 → [0, 1, 3]
3 → [0, 2]- 장점: 메모리 효율적 (
O(V + E)) - 단점: 간선 존재 여부 확인에
O(degree)소요
💡 코딩 테스트에서는 대부분 인접 리스트 방식을 사용한다.
ArrayList<ArrayList<Integer>>로 구현하면 조회 성능도 좋고 구현도 간편함
2. DFS (깊이 우선 탐색, Depth-First Search)
2-1. 개념
DFS는 한 방향으로 갈 수 있는 끝까지 탐색한 뒤, 더 이상 갈 곳이 없으면 이전 갈림길로 돌아와서 아직 방문하지 않은 노드를 탐색하는 방식이다.
스택(Stack) 자료구조를 이용하며, 구체적인 동작 과정은 다음과 같습니다:
- 탐색 시작 노드를 스택에 삽입하고 방문 처리한다.
- 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
- 두 번째 과정을 더 이상 수행할 수 없을 때까지 반복한다.
2-2. 의사 코드 (Pseudocode)
dfs(V, E, R) { // V: 정점 집합, E: 간선 집합, R: 시작 정점
visited[R] <- YES; // 시작 정점 R을 방문했다고 표시
for each x ∈ E(R) // E(R): 정점 R의 인접 정점 집합 (정점 번호를 오름차순으로 방문)
if (visited[x] = NO) then dfs(V, E, x);
}2-3. 구현 방법
DFS는 두 가지 방법으로 구현할 수 있다.
- 재귀(Recursion) 를 이용하여 백트래킹 방식으로 구현
- 명시적 Stack 을 이용하여 구현
재귀를 이용하는 방식이 코드가 훨씬 간결하고 직관적이므로, 아래에서는 재귀 방식을 중심으로 설명합니다.
2-4. Java 구현 (재귀 + 인접 리스트)
import java.io.*;
import java.util.*;
public class DFS {
static ArrayList<ArrayList<Integer>> adj_list;
static int[] visited;
static int count;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken()); // 정점의 수
int M = Integer.parseInt(st.nextToken()); // 간선의 수
int R = Integer.parseInt(st.nextToken()); // 시작 정점
// 방문 순서 배열 (0이면 미방문)
visited = new int[N + 1]; // 1번 정점부터 사용
for (int i = 1; i < N + 1; i++) {
visited[i] = 0;
}
// 인접 리스트 초기화
adj_list = new ArrayList<>();
for (int i = 0; i <= N; i++) { // 0번 인덱스는 더미
adj_list.add(new ArrayList<Integer>());
}
// 간선 입력
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int first = Integer.parseInt(st.nextToken());
int second = Integer.parseInt(st.nextToken());
adj_list.get(first).add(second);
adj_list.get(second).add(first); // 무방향 그래프
}
// 오름차순 정렬 (정점 번호가 작은 것부터 방문)
for (int i = 1; i <= N; i++) {
adj_list.get(i).sort(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o1 - o2;
}
});
}
count = 1; // 시작 정점의 방문 순서는 1
dfs(R);
// 결과 출력
for (int i = 1; i <= N; i++) {
System.out.println(visited[i]);
}
}
private static void dfs(int R) {
visited[R] = count; // 정점 R의 방문 순서를 기록
for (int i = 0; i < adj_list.get(R).size(); i++) {
int newNode = adj_list.get(R).get(i); // 인접 노드
if (visited[newNode] == 0) { // 미방문 노드라면
count++;
dfs(newNode); // 재귀 호출
}
}
}
}핵심 포인트 정리:
ArrayList<ArrayList<Integer>>로 이중 리스트를 구성하여 인접 리스트를 만든다.visited[]배열로 방문 여부 + 방문 순서를 동시에 관리한다 (0이면 미방문).- 인접 리스트를 오름차순 정렬해서 정점 번호가 작은 것부터 방문한다.
- 재귀 호출로 자연스럽게 스택처럼 동작한다 (콜 스택 활용).
3. BFS (너비 우선 탐색, Breadth-First Search)
3-1. 개념
BFS는 루트 노드에서 가장 인접한 노드부터 탐색하는 방법이다. DFS와 달리 재귀적으로 동작하지 않으며, 큐(Queue) 자료구조를 사용한다.
따라서 어떤 노드를 방문하였는지를 반드시 검증해야 한다.
3-2. 의사 코드 (Pseudocode)
bfs(V, E, R) { // V: 정점 집합, E: 간선 집합, R: 시작 정점
for each v ∈ V - {R}
visited[v] <- NO;
visited[R] <- YES; // 시작 정점 R을 방문 표시
enqueue(Q, R); // 큐 맨 뒤에 시작 정점 R을 추가
while (Q ≠ ∅) {
u <- dequeue(Q); // 큐 맨 앞쪽의 요소를 꺼냄
for each v ∈ E(u) // 정점 u의 인접 정점 집합 (오름차순으로 방문)
if (visited[v] = NO) then {
visited[v] <- YES; // 방문 표시
enqueue(Q, v); // 큐 맨 뒤에 추가
}
}
}3-3. 동작 과정
- 시작 정점을 방문 표시하고 큐에 넣는다.
- 큐가 빌 때까지 반복:
- 큐에서 정점 하나를 꺼낸다.
- 꺼낸 정점의 인접 정점을 탐색한다.
- 방문하지 않은 인접 정점이 있다면 → count를 늘리고, 방문 표시 후 큐에 넣는다.
3-4. Java 구현 (큐 + 인접 리스트)
import java.io.*;
import java.util.*;
public class BFS {
static ArrayList<ArrayList<Integer>> adj_list;
static int[] visited;
static int count;
static ArrayDeque<Integer> deque = new ArrayDeque<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken()); // 정점의 수
int M = Integer.parseInt(st.nextToken()); // 간선의 수
int R = Integer.parseInt(st.nextToken()); // 시작 정점
// 방문 순서 배열
visited = new int[N + 1];
for (int i = 1; i < N + 1; i++) {
visited[i] = 0;
}
// 인접 리스트 초기화
adj_list = new ArrayList<>();
for (int i = 0; i <= N; i++) {
adj_list.add(new ArrayList<Integer>());
}
// 간선 입력
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int first = Integer.parseInt(st.nextToken());
int second = Integer.parseInt(st.nextToken());
adj_list.get(first).add(second);
adj_list.get(second).add(first);
}
// 오름차순 정렬
for (int i = 1; i <= N; i++) {
adj_list.get(i).sort(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o1 - o2;
}
});
}
count = 1;
bfs(R);
// 결과 출력
for (int i = 1; i <= N; i++) {
System.out.println(visited[i]);
}
}
private static void bfs(int R) {
visited[R] = count;
deque.offer(R); // 큐 맨뒤에 넣기
while (!deque.isEmpty()) { // 큐가 공백이 아닌 경우
int newNode = deque.pollFirst(); // 큐에서 꺼내기
for (int i = 0; i < adj_list.get(newNode).size(); i++) {
int innerNode = adj_list.get(newNode).get(i);
if (visited[innerNode] == 0) { // 미방문 노드
count++;
visited[innerNode] = count;
deque.offer(innerNode); // 큐에 추가
}
}
}
}
}핵심 포인트 정리:
ArrayDeque를 큐로 사용한다 (offer로 삽입,pollFirst로 꺼냄).- BFS에서는 큐에 넣는 시점에 방문 처리하는 것이 중요하다 (꺼낼 때가 아님!).
- DFS 코드와 구조가 거의 동일하며, 핵심 차이는 재귀 → 큐 반복문으로 바뀐 것뿐이다.
4. DFS vs BFS: 언제 무엇을 쓸까?
4-1. 모든 정점을 방문하는 것이 주요한 문제
단순히 모든 정점을 방문하는 것이 중요한 경우, DFS와 BFS 두 가지 방법 중 어느 것을 사용해도 상관없습니다. 둘 중 편한 것을 사용하면 된다.
4-2. 경로의 특징을 저장해야 하는 문제 → DFS
예를 들어 각 정점에 숫자가 적혀있고, a부터 b까지 가는 경로에 같은 숫자가 있으면 안 되는 문제처럼, 각각의 경로마다 특징을 저장해야 할 때는 DFS를 사용한다.
BFS는 경로의 특징을 가지지 못한다.
4-3. 최단거리를 구해야 하는 문제 → BFS (중요!)
미로 찾기 등 최단거리를 구해야 할 경우, BFS가 유리하다.
왜냐하면 DFS는 깊이 우선으로 경로를 검색하기 때문에 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만, BFS는 현재 노드에서 가까운 곳부터 찾기 때문에 경로 탐색 시 먼저 찾아지는 해답이 곧 최단거리이기 때문이다.
4-4. 기타 선택 기준
- 검색 대상 그래프가 정말 크다면 → DFS 고려
- 검색 대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않다면 → BFS
5. BFS가 왜 최단거리를 보장하는가?
이 부분은 자주 헷갈리는 개념이므로 별도로 정리
5-1. 핵심 원리: 레벨 단위 탐색
BFS는 큐 구조를 사용하며, 시작점에서 가까운 곳부터 탐색을 합니다. 시작 정점을 기준으로 그래프는 거리(레벨) 별로 나뉜다.
거리 0 : 시작 정점 V
거리 1 : V와 직접 연결된 정점들
거리 2 : 거리 1에서 한 번 더 이동한 정점들
거리 3 : ...BFS는 이 순서를 강제로 지킨다.
이유:
- 시작 정점 V를 큐에 넣음
- V를 꺼내서 → 거리 1 정점들을 큐에 넣음
- 거리 1 정점들이 모두 처리된 후에야 거리 2 정점들이 큐에서 나오기 시작함
👉 큐 구조 때문에 레벨을 건너뛰는 게 물리적으로 불가능.
5-2. 즉, 처음 도착한 순간이 곧 최단 거리
BFS에서 어떤 노드에 처음 도착하는 순간의 거리가 바로 최단 거리이다. 이미 방문한 곳은 다시 계산하지 않으므로, 나중에 더 긴 경로로 도착하는 경우는 무시된다.
5-3. DFS는 왜 최단거리를 보장 못할까?
DFS는 시작 → 한 방향 끝까지 → 막히면 돌아옴 방식으로 동작합니다.
예를 들어:
A → B → C → D (거리 3)
A → E (거리 1)DFS는 D를 먼저 만날 수도 있지만, 최단거리는 E(거리 1)입니다.
👉 DFS는 깊이 우선이지, 거리 우선이 아니다.
5-4. BFS 최단거리 성립 조건
⚠️ BFS가 최단거리를 보장하려면 다음 조건이 필요합니다:
- 모든 간선의 가중치가 동일해야 합니다 (보통 1).
- 그래프가 무방향 or 단방향 — 상관없음.
- 처음 방문 시 방문 처리를 해야 합니다.
❌ 가중치가 다르면? → 다익스트라(Dijkstra) 알고리즘을 사용해야 된다.
6. 한눈에 보는 DFS vs BFS 비교
| 항목 | DFS | BFS |
|---|---|---|
| 자료구조 | 스택 (또는 재귀) | 큐 |
| 탐색 방식 | 깊이 우선 (한 방향 끝까지) | 너비 우선 (가까운 것부터) |
| 최단거리 보장 | ❌ | ✅ (가중치 동일 시) |
| 경로 특징 저장 | ✅ | ❌ |
| 구현 난이도 | 재귀로 간단 | 큐 사용으로 간단 |
| 메모리 | 경로 길이에 비례 | 너비에 비례 |
| 적합한 문제 | 백트래킹, 경로 탐색 | 최단거리, 레벨 탐색 |
마무리
DFS와 BFS는 그래프 탐색의 기본이면서, 코딩 테스트에서 가장 자주 출제되는 유형. 두 알고리즘의 동작 원리를 확실히 이해하고, 문제 유형에 따라 적절한 것을 선택할 수 있어야 한다.
특히 "최단거리 문제는 BFS"라는 공식을 외우는 것에서 그치지 말고, 왜 BFS가 최단거리를 보장하는지 (레벨 단위 탐색 + 큐의 FIFO 특성) 원리까지 이해해두면 응용 문제 또한 잘 풀수 있다.
📌 연습 추천 문제 (백준)
