안녕하세요!
드디어 그래프 이론을 활용한 알고리즘 공부를 하고 있습니다.
이론을 정리하고 문제 푸는 게 재미있지만 시간이 좀 걸리는 작업이기는 하네요 ㅎㅎ
제가 한창 알고리즘 공부할 때 정말 재미있게 배웠던 그래프 알고리즘 중,
가장 많이 활용되고 기본적으로 쓰이는 탐색 알고리즘을 공부해보겠습니다 :)
이번에는 DFS 알고리즘을 정리해보려고 합니다~
DFS의 정의 (깊이 우선 탐색)
🔹 깊이 우선 탐색/DFS(Depth-First-Search) 란?
: 그래프 또는 트리에서 한 정점에서 시작하여, 한 방향으로 갈 수 있는 곳 까지 끝까지 깊이 탐색한 후,
더 이상 갈 곳이 없으면 다시 돌아와서(백트래킹) 다른 경로를 탐색하는 알고리즘입니다.
🔹 DFS의 특징
| 항목 | 설명 |
| 탐색 방식 | 깊이 우선 (먼저 한 쪽 끝까지 파고 듦) |
| 자료구조 | 스택 (재귀 호출 시 내부 스택 사용) |
| 방문 순서 | 정점 방문 시 즉시 처리 (즉시 방문 + 재귀) |
| 시간복잡도 | O(V + E) (V: 정점 수, E: 간선 수) |
| 사용 구조 | 그래프, 트리, 백트래킹, 경로탐색 등 |
| 구현 방식 | 재귀 함수, 또는 명시적 스택 사용 |
🔹 예시 그래프 구조
: 이해를 돕기 위하여 그래프를 아래와 같이 그려보았습니다.
정점: 0, 1, 2, 3, 4
간선: 0-1, 0-2, 0-3, 1-3, 2-3, 3-4
그림으로 나타내면 아래와 같습니다.
🔹 DFS 예제 코드 (Java)
DFS 예제 코드는 아래와 같이 작성할 수 있습니다.
Java를 기반으로 작성된 코드인데요,
우선은 각 노드를 순회하면서 방문한 노드를 출력하도록 구현하였습니다.
import java.util.*;
public class DFSExample {
static List<List<Integer>> graph = new ArrayList<>();
static boolean[] visited;
public static void dfs(int node) {
visited[node] = true;
System.out.print(node + " "); // 방문 시 출력
for (int next : graph.get(node)) {
if (!visited[next]) {
dfs(next);
}
}
}
public static void main(String[] args) {
int n = 5; // 정점 수
visited = new boolean[n];
// 그래프 초기화
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
// 양방향 간선 추가
graph.get(0).add(1); graph.get(1).add(0);
graph.get(0).add(2); graph.get(2).add(0);
graph.get(0).add(3); graph.get(3).add(0);
graph.get(1).add(3); graph.get(3).add(1);
graph.get(2).add(3); graph.get(3).add(2);
graph.get(3).add(4); graph.get(4).add(3);
// DFS 탐색 시작
dfs(0);
}
}이 코드를 바탕으로 출력 결과는 아래와 같이 확인할 수 있습니다.
출력 결과
0 1 3 4 2
이때 출력 결과는, 간선의 방문 순서에 따라서 출력 결과는 달라질 수 있습니다.
위 코드에서는 add 순서대로 0 노드에서 1노드를 먼저 방문한 출력 결과입니다.
DFS를 활용한 문제 해결
DFS를 활용하여 다양한 유형의 문제를 해결할 수 있는데요,
어떤 문제는 BFS로도 해결이 가능하지만, 그렇지 않은 경우도 있습니다.
표 형태로 정리해보자면 아래와 같습니다.
BFS는 별도 포스팅으로 정리해볼 예정입니다.
하지만 DFS, BFS 모두 그래프를 탐색하는 알고리즘이기 때문에 살짝 비교해보겠습니다 :)
🔹 DFS로 해결 가능한 문제 유형 정리
| 문제유형 | 설명 | DFS 가능 여부 | BFS 가능 여부 |
| 모든 경로 찾기 | 두 노드 간 가능한 모든 경로 찾기 | 🟢 | ❌ |
| 조합 / 순열 생성 | 백트래킹 기반으로 경우의 수 탐색 | 🟢 | ❌ |
| 미로의 모든 탈출 경로 찾기 | 출구가 여러개인 경우, 모든 경로 추적 | 🟢 | ❌ (최단 경로만 찾을 수 있음) |
| 사이클 탐지 | 방문중 노드를 다시 방문하면 사이클 존재 | 🟢 | 🟢 |
| 트리의 순회 (전위/중위/후위) | DFS 기반으로 트리 순회 | 🟢 | ❌ |
| 그래프의 연결 요소 수 구하기 | DFS/BFS를 여러 번 호출하여 요소 개수 구함 | 🟢 | 🟢 |
| 위상정렬 (DFS 후 스택에 저장) | DAG에 대해 DFS후 역순 정렬 | 🟢 | 🟢 (Kahn 알고리즘) |
| 강한 연결 요소 (SCC) | Kosaraju / Tarjan 알고리즘 | 🟢 | ❌ |
| 단절점 / 단절선 찾기 | DFS 트리의 low-link값 활용 | 🟢 | ❌ |
| DFS 기반 시뮬레이션 | 방문하며 탐색하는 시뮬레이션 문제 (예: 퍼즐) | 🟢 | ❌ |
| Flood Fill (색 채우기) | DFS/BFS 모두 사용 가능 | 🟢 | 🟢 |
| 그래프 탐색 순서 저장 | 경로를 순서대로 저장해야할 때 유리 | 🟢 | ❌ |
| 백 트래킹 탐색 (N-Queen, Sudoku) | 상태 복원하며 가지치기 | 🟢 | ❌ |
| 경로가 존재하는지만 확인 | DFS/BFS 로 도달 여부 판단 | 🟢 | 🟢 |
| 최단 거리 탐색 | 가중치 없는 그래프에서 거리 최소값 | 🟢 (비효율적) | 🟢 (정답 보장) |
| 가중치 있는 최단경로 | Dijkstra / Bellman-Ford 등 필요 | ❌ | ❌ (특화 알고리즘 필요) |
🔹 DFS vs BFS 간 비교
| 항목 | DFS | BFS |
| 탐색 방식 | 깊이 우선 | 너비 우선 |
| 자료구조 | 스택/재귀 | 큐 |
| 장점 | 경로 추적, 백트래킹 적합 | 최단 거리 탐색에 적합 |
| 단점 | 깊이가 깊을 경우 StackOverflow 위험 | 공간 사용이 많을 수 있음 |
| 용도 | 조합, 퍼즐, 트리 탐색, 사이클 탐지 | 최단거리, BFS 트리 구성, 레벨 탐색 |
반면, 반드시 DFS 를 사용해야하는 경우도 있습니다.
간단히 정리해보면, 아래 표와 같이 나타낼 수 있습니다 :)
🔹 반드시 DFS를 사용해야하는 대표 문제 유형 예시
| 문제 | 설명 |
| N-Queen | DFS + 백트래킹 없이는 탐색 불가 |
| 부분 집합 / 조합 | DFS로 상태 트리 구성 필요 |
| 미로의 모든 경로 | BFS는 최단 경로만 찾을 수 있음 |
| 연결 요소 탐색 + 경로 저장 | BFS보다 DFS가 경로 추적에 유리 |
| Tarjan 알고리즘 | DFS 기반의 Low-link 개념 필수 |
즉, 아래와 같이 정리할 수 있습니다.
1. DFS는 모든 경로, 조합, 경로 추적, 재귀적 해결이 필요한 문제에서 유리합니다.
2. BFS는 최단거리나 레벨별 탐색에서 유리합니다.
3. DFS는 보통 재귀 함수로 구현되며, 스택 구조를 갖고 있습니다.
4. 두 가지 모두의 방법으로 해결할 수 있는 문제도 있지만, 목적에 따라 효율이 다릅니다.
DFS 시간복잡도
🔹 DFS 의 시간복잡도
DFS의 시간 복잡도는
O(V + E)
입니다.
- V: 정점(Vertex) 의 수
- E: 간선(Edge)의 수
🔹 시간복잡도 설명
시간복잡도는 왜 O(V + E) 일까요?
먼저,
DFS는 각 호출마다 다음을 수행합니다:
1. 정점 방문
: visited[] 배열을 통해 각 정점을 딱 1번 씩 만 방문합니다.
-> O(V)
2. 인접 리스트를 통해 간선 순회
각 정점에서 연결된 간선을 순회합니다.
인접 리스트 구조에서는 총 간선 수 만큼 for 문이 동작합니다.
-> O(E)
따라서, 아래와 같이 결론을 내릴 수 있습니다.
총 탐색 시간 = 정점 방문 시간 + 간선 순회 시간 = O(V + E)
🔹 인접리스트 vs 인접 행렬 에서의 시간복잡도 비교
| 표현 방식 | 시간복잡도 | 공간복잡도 | 설명 |
| 인접 리스트 | O(V + E) | O(V + E) | 회소 그래프에 유리 |
| 인접 행렬 | O(V^2) | O(V^2) | 밀집 그래프나 간선 개수 많을 때 불리 |
위 비교를 예시를 들면 아래와 같습니다.
* V = 10,000, E = 10,000 일 때 -> 리스트: 빠름
* V = 1,000 -> 행렬: 1,000^2 = 1,000,000 -> 느림
🔹 DFS 시간복잡도 증명(인접리스트 기준)
1. 모든 정점 V에 대해
if (!visited[v]) dfs(v); // 최대 V번
2. DFS 함수 내부
for (int next : graph.get(v)) {
if (!visited[next]) dfs(next);
}
-> graph.get(v)는 정점 v의 인접 리스트
-> 즉, 모든 간선을 한 번씩 순회
-> 정점의 개수 만큼 dfs() 호출, 간선 개수 만큼 반복문 수행
따라서 총 시간복잡도는 O(V+E) 가 됩니다.
🔹 특수한 경우들
그 외에도 특수한 경우들에는 시간복잡도가 달라질 수 있습니다.
몇 가지 경우의 수를 간단히 정리해 보면 아래와 같이 정리할 수 있습니다.
| 그래프 구조 | 간선 수 E | 시간 복잡도 |
| 트리 (N개의 구조) | E = V - 1 | O(V) |
| 완전 그래프 (정점마다 모두 연결) | E = V(V-1)/2 | O(V^2) |
| 방향 그래프 | 방향에 따라 E <= V(V-1) | O(V + E) 유지 |
❗️예외: DFS에 조건 추가 시 시간 복잡도 증가
DFS에 조건을 추가할 경우 시간복잡도가 증가할 수 있습니다.
대표적으로 예를 들면 백트래킹과 조합/순열 생성의 경우가 있습니다:
* 백트래킹: 모든 경로를 확인 할 경우 -> 경우의 수 만큼 시간 증가
* 조합/순열 생성: O(N!) 또는 O(2^N) 가능
dfs(level + 1); // 이 호출이 모든 가능한 분기를 방문할 시 O(2^n)
✅ 마무리 정리
| 항목 | 내용 |
| 기본 시간 복잡도 | O(V + E) |
| 자료구조에 따라 | 인접리스트: O(V + E), 행렬: O(V^2) |
| 공간복잡도 | O(V) (Visited 배열 + 호출 스택) |
| 적용 조건 | 그래프가 연결되지 않아도 전체 정점을 검사해야 함 |
| 확장 시 | 백트래킹, 조합 등과 결합 시 지수 시간복잡도 가능성 있음 |
시간복잡도에 대해서는 이정도로 정리해볼 수 있습니다 !
DFS에서의 백트래킹을 적용할 때와 그렇지 않을 때의 차이
공부를 하다보니, 저도 궁금해진 내용이 있어서 추가로 정리해 보았습니다.
DFS는 백트래킹 시 많이 사용한다고 하는데요,
그렇다면 DFS에서 백트래킹을 적용할 때와 그렇지 않을 때의 차이점은 무엇일까요?
그 차이는 바로 탐색의 목적과 경로를 얼마나 기억하고 관리하느냐에 따라 달라집니다.
DFS vs 백트래킹의 개념적 차이를 정리하면 다음과 같습니다:
| 구분 | DFS (기본) | DFS (백트래킹) |
| 목적 | 정점 전체를 방문하는 탐색 | 가능한 경로 or 조합을 찾기 위한 모든 경로 탐색 |
| 경로 추적 | 현재 노드만 신경 씀 | 경로 전체를 기억하고, 되돌아가서 다른 경로도 탐색 |
| 상태 복원 | 필요 없음 | 방문 여부, 경로 등 복원 필수 |
| 사용 사례 | 연결 여부 확인, 사이클 탐색 | 조합, 경로 찾기, 미로 탐색, N-Queen 등 |
간단히 예시를 들어보겠습니다.
🔹 예제 문제: 그래프의 모든 경로 출력
문제: 양방향 그래프가 주어졌을 때, 0번 노드에서 3번 노드까지 가는 모든 경로를 출력하시오
1) 단순 DFS 예제 - 백 트래킹 없이
public static void dfsNoBacktrack(int now) {
if (now == 3) {
System.out.println("도착!"); // 도착 알림
return;
}
visited[now] = true;
for (int next : graph.get(now)) {
if (!visited[next]) {
dfsNoBacktrack(next);
}
}
}
* 탐색은 되지만, 경로 자체는 알 수 없음
* 여러 경로를 찾기 어려움
* 도착했는지 여부만 알 수 있을 뿐, 어떤 경로로 도달했는지는 기록되지 않음
2) DFS + 백트래킹 예제 - 경로 출력
public static void dfsBacktrack(int now, List<Integer> path) {
path.add(now);
if (now == 3) {
System.out.println(path); // 현재까지의 경로 출력
} else {
visited[now] = true;
for (int next : graph.get(now)) {
if (!visited[next]) {
dfsBacktrack(next, path);
}
}
visited[now] = false; // 백트래킹 – 방문 복원
}
path.remove(path.size() - 1); // 백트래킹 – 경로 복원
}* 모든 가능한 경로를 찾아낼 수 있음
출력 예시
0 -> 1 -> 3
0 -> 2 -> 3
...
🔹 핵심 차이 정리
| 기능 | DFS 만 사용 | DFS + 백트래킹 사용 |
| 전체 정점 탐색 | O | O |
| 경로 출력 | X | O |
| 중복 결론 탐색 | X | O |
| 상태 복원 (visited 등) | 필요없음 | 필요함 |
| 대표 활용 | 연결 여부, 사이클 탐색 | 조합/순열, 경로 탐색, 미로 문제 |
쉽게 정리하자면,
* DFS 만 사용하는 경우
목적지에 도달하기만 하면 OK -> 길이든 뭐든 상관 없음
* DFS + 백트래킹 하는 경우
모든 길을 하나도 빠짐 없이 조사하라. -> 그리고 갈 때 마다 노트에 길을 적고, 돌아올 때는 지운다.
라고 정리해볼 수 있겠습니다 :)
예제 문제 풀이: BOJ 2606 바이러스
* 예제 문제: BOJ 2606 바이러스
링크: https://www.acmicpc.net/problem/2606
문제:
웜 바이러스는 네트워크를 통해 전파된다.
한 컴퓨터가 감염되면 네트워크 상으로 연결되어있는 컴퓨터들에 모두 바이러스가 전파된다.
1번 컴퓨터가 감염되었을 때 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터 수를 구하기.
즉, 네트워크(그래프) 정보가 주어졌을 때 노드 1번에서 시작하는 연결요소를 확인하고,
1을 제외한 연결요소 내의 노드 수를 구하는 문제입니다.
이 때, 주어지는 그래프는 직접 연결된 정보만 주어집니다.
따라서 연결 정보는 두 노드간 간선에 대한 정보입니다. (경로 정보 x)
🔹 문제 풀이 순서
1. 주어진 데이터로 그래프 구성
2. 그래프 탐색 구현
3. 결과 데이터 세팅
저는 위와 같은 문제풀이 순서로 해결하였습니다.
소스 코드는 아래와 같이 작성하였습니다.
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int v = input.nextInt();
int e = input.nextInt();
// 그래프 초기화
List<List<Integer>> network = new ArrayList<>();
for(int i = 0; i <= v; ++i) {
network.add(new ArrayList<>());
}
// 그래프 구성
for(int i = 0; i < e; i++) {
int a = input.nextInt();
int b = input.nextInt();
network.get(a).add(b);
network.get(b).add(a);
}
boolean[] visited = new boolean[v + 1];
int result = dfs(1, visited, network);
// 결과 출력
System.out.println(result - 1);
}
아래는 DFS 를 구현한 부분입니다.
public static int dfs(int vertex, boolean[] visited, List<List<Integer>> graph) {
int cnt = 0;
visited[vertex] = true;
cnt++;
for(int next: graph.get(vertex)) {
if(!visited[next]) {
cnt += dfs(next, visited, graph);
}
}
return cnt;
}
❗️ 마지막에 출력 시 -1을 해준 이유는,
DFS에서는 방문 시 노드 수를 count해주고 있으므로 출발 노드인 1을 개수에서 제외하기 위함입니다.
DFS 캡쳐본도 첨부하면 아래와 같습니다.
기본적인 DFS 탐색에 노드 수를 세는 부분만 추가해주었습니다.
이번에는 연결 요소를 구하는 문제였습니다.
이번 문제는 DFS를 이해하기 위한 기초 문제를 골라보았습니다.
이런식으로 dfs를 활용하여 연결요소를 구하고, 여기에 필요한 부분을 추가하여 문제 해결이 가능합니다.
DFS를 비롯한 그래프 관련 문제들이 처음에 이해하기 어려울 수 있지만,
제대로 파악하고 나면 문제를 풀 때 참 재미있었습니다.
'실제 생활 속 요소들을 나타낼 수 있는' 그래프의 특성상 보다 다양한 문제들을 풀 수 있어서 재미가 더해진 것도 같아요!ㅎㅎ
코딩테스트를 준비하면 보통 그래프 알고리즘도 범위에 들어가더라고요.
이번 기회에 저도 확실히 정리하고 갑니다 ㅎㅎ
알고리즘을 공부하시는분들께도 도움이 되는 포스팅이었길 바랍니다 !
