깊이 우선 탐색(DFS: depth-first search)은 그래프 완전 탐색 기법 중 하나이다. 깊이 우선 탐색은 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다.
| 기능 | 특징 | 시간 복잡도 (노드 수: V, 에지 수: E) |
| 그래프 완전 탐색 | - 재귀 함수로 표현 - 스택 자료구조 이용 |
O(V+E) |
깊이 우선 탐색은 실제 구현 시 재귀 함수를 사용하기 때문에 스택 오버플로에 유의해야 한다. 깊이 우선 탐색을 응용하여 풀 수 있는 문제는 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 등이 있다.
핵심 이론
1. DFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기
- DFS를 위해 필요한 초기 작업은 인접 리스트로 그래프 표현하기, 방문 배열 초기화하기, 시작 노드 스택에 삽입하기이다.
- 스택에 시작 노드를 1로 삽입할 때 해당 위치의 방문 배열을 체크하면 T,F,F,F,F,F가 된다.
2. 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입하기
- pop을 수행하여 노드를 꺼낸다.
- 꺼낸 노드를 탐색 순서에 기입하고 인접 리스트의 인접 노드를 스택에 삽입하며 방문 배열을 체크한다. 방문 배열은 T,T,T,F,F,F가 된다.
3. 스택 자료구조에 값이 없을 때까지 반복하기
- 앞선 과정을 스택 자료구조에 값이 없을 때까지 반복한다.
- 이때 이미 다녀간 노드는 방문 배열을 바탕으로 재삽입하지 않는 것이 핵심이다.
이어서 설명하면 스택에서 3을 꺼내며 탐색 순서에 기록하고 인접 노드 4를 스택에 삽입하며 방문 배열에 체크한다. 4를 꺼내며 탐색 순서에 기록하고 6을 삽입하며 방문 배열에 체크한다. 6을 꺼내며 탐색 순서에 기록하고 6과 인접한 노드는 없으므로 추가 삽입은 없다. 계속해서 스택에서 2를 꺼내며 탐색 순서에 기록하고 2와 인접한 5,6을 삽입하기 위해 보는데 이때 6은 방문 배열에 T로 체크되어 있으므로 5만 삽입한다. 이 과정을 스택이 빌 때까지 진행한다.
스택에 노드를 삽입할 때 방문 배열을 체크하고, 스택에서 노드를 뺄 때 탐색 순서에 기록하며 인접 노드를 방문 배열과 대조하여 살펴본다.
[백준 11724번] 연결 요소의 개수
https://www.acmicpc.net/problem/11724
노드의 최대 개수가 1,000이므로 시간 복잡도 N^2 이하의 알고리즘을 모두 사용할 수 있다. 연결 요소는 에지로 연결된 노드의 집합이며, 한 번의 DFS가 끝날 때까지 탐색한 모든 노드의 집합을 하나의 연결 요소로 판단할 수 있다.
1. 그래프를 인접 리스트로 저장하고 방문 배열도 초기화한다. 방향이 없는 그래프이기 때문에 양쪽 방향으로 에지를 모두 저장한다.
2. 임의의 시작점에서 DFS를 수행한다. (현재 경우 1로 시작, 탐색 마친 후 방문한 곳은 1, 2, 5가 됨)
3. 아직 방문하지 않은 노드가 있으므로 시작점 다시 정해 탐색을 진행한다. 3, 4, 6 순서로 탐색을 마친 후 모든 노드를 방문했으므로 전체 탐색을 종료한다.
4. 1~3 과정을 통해 총 2번의 DFS가 진행되었다는 것을 알 수 있다. 즉 연결 요소 개수는 2개이다.
만약 그래프가 모두 연결되어 있었다면 DFS는 1번 실행되었을 것이다. 즉, 모든 노드를 탐색하는 데 실행한 DFS의 실행 횟수가 곧 연결 요소 개수와 같다.
책에서는 스택 대신 재귀 함수를 이용하여 풀었다. 난 스택으로 풀었는데 틀렸다. 똑같이 풀었는데 왜 틀렸는지 잘 모르겠다가도 코드가 너무 더러워서 디버깅 하기도 싫어진다. 그냥 정답 보고 방식 익혀두는게 낫겠다.
[정답]
import java.io.*;
import java.util.*;
public class Main {
static ArrayList<Integer>[] A;
static boolean visited[];
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());
A = new ArrayList[n + 1];
visited = new boolean[n + 1];
for (int i = 1; i <= n; i++) { // 인접 리스트 초기화
A[i] = new ArrayList<Integer>();
}
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
A[s].add(e); // 양방향 에지이므로 양쪽에 에지 더하기
A[e].add(s);
}
int count = 0;
for (int i = 1; i < n + 1; i++) {
if (!visited[i]) { // 방문하지 않은 노드가 없을 때까지 반복하기
count++;
DFS(i);
}
}
System.out.println(count);
}
static void DFS(int v) {
if(visited[v])
return;
visited[v] = true;
for (int i : A[v]) {
if(!visited[i]) // 연결 노드 중 방문하지 않았던 노드만 탐색하기
DFS(i);
}
}
}
[원본]
import java.io.*;
import java.util.*;
public class Main {
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());
// 인접 리스트 만들기
LinkedList[] list = new LinkedList[N+1];
for (int i = 1; i <= N; i++) {
list[i] = new LinkedList<Integer>();
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
list[u].add(v);
list[v].add(u);
}
// 방문 배열 & 스택
boolean[] visited = new boolean[N+1];
Stack<Integer> stack = new Stack<>();
int answer = 0;
stack.push(1); // 시작 노드 스택에 삽입
visited[1] = true; // 시작 노드 방문함
boolean allVisited = false; // while문 조건
while(!allVisited) {
if(stack.isEmpty()) { // 스택 빔 -> 해당 그래프 전부 돎. 새로운 그래프 찾고 돌기
answer++; // 새로운 그래프라는 뜻으로 정답 1증가
int count = 0;
for (int i = 1; i <= N; i++) {
if(!visited[i]) { // 만약 돌지 않은 노드가 있다면
stack.push(i); // 해당 노드 stack에 push
visited[i] = true; // 해당 노드 돎
} else count++;
}
if(count == N) allVisited = true; // 만약 전부 방문 -> while 탈출
}
else {
int num = stack.pop(); // 스택 pop, 해당 값 인접 리스트 돌기
for (int i = 0, n = list[num].size(); i < n; i++) {
int listNum = (Integer)list[num].poll();
if(!visited[listNum]) { // 만약 방문하지 않은 노드라면
stack.push(listNum); // stack에 push 후 방문 배열에 표시
visited[listNum] = true;
}
}
}
}
System.out.println(answer);
}
}
[백준 2023번] 신기한 소수
https://www.acmicpc.net/problem/2023
재귀 함수 이용한 DFS 문제를 많이 풀어보자. 재귀 함수의 원리를 잘 이해하면 문제 조건에 맞도록 코드를 수정하기 쉬울 것이다. 이 문제는 재귀 함수에 자릿수 개념을 붙여 구현한다. 또한 문제 조건에 맞도록 가지치기도 해보겠다.
소수는 약수가 1과 자기 자신인 수를 말한다. 예를 들어 4는 약수가 1, 2, 4이므로 소수가 아니고 7은 1, 7이므로 소수이다. 참고로 1은 소수가 아니고, 2는 소수에 속한다.
자릿수가 한 개인 소수는 2, 3, 5, 7이므로 이 수부터 탐색을 시작한다. 4, 6, 8, 9를 제외한 가지치기 방식을 적용한 것이다. 이어서 자릿수가 두 개인 현재 수 * 10 + a를 계산하여 이 수가 소수인지 판단하고, 소수라면 재귀 함수로 자릿수를 하나 늘린다. 단, a가 짝수인 경우는 항상 2를 약수로 가지므로 가지치기로 a가 짝수인 경우를 제외한다. 이런 방식으로 자릿수를 N까지 확장했을 때 그 값이 소수라면 해당 값을 출력한다.
첫 탐색 배열, 중간 탐색 배열을 가지치기하고 중간 탐색 과정에서 소수가 아닌 경우 멈추는 가지치기도 포함되어 있으므로 시간 복잡도를 잘 줄여 문제를 풀 수 있다.
[정답]
import java.io.*;
import java.util.*;
public class Main {
static int N;
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
DFS(2, 1); // 일의 자리 소수는 2, 3, 5, 7이므로 4개 수에서만 시작
DFS(3, 1);
DFS(5, 1);
DFS(7, 1);
}
static void DFS(int number, int jarisu) {
if(jarisu == N) {
if(isPrime(number)) {
System.out.println(number);
}
return;
}
else {
for (int i = 1; i < 10; i++) {
if(i % 2 == 0) continue; // 짝수라면 더 이상 탐색할 필요가 없음
if(isPrime(number * 10 + i)) // 소수라면 재귀 함수로 자릿수 늘림
DFS(number * 10 + i, jarisu + 1);
}
}
}
static boolean isPrime(int num) { // 소수인지 찾는 메소드
for (int i = 2; i <= num / 2; i++)
if(num % i == 0)
return false;
return true;
}
}
[백준 13023번] ABCDE
https://www.acmicpc.net/problem/13023
문제에서 요구하는 A, B, C, D, E 관계는 재귀 함수의 형태와 비슷하다. 주어진 모든 노드에 DFS를 수행하고 재귀의 깊이가 5 이상 (5개의 노드가 재귀 형태로 연결)이면 1, 아니라면 0을 출력한다. DFS의 시간 복잡도는 O(V+E)이므로 최대 4,000, 모든 노드를 진행했을 때 4,000 * 2,000, 즉 8,000,000이므로 DFS를 사용해도 제한 시간 내에 문제를 풀 수 있다.
난 첫 문제를 풀었던 것처럼 끝까지 돌면서 count를 세다가 다시 돌아오면 visited 배열을 돌며 안 돌았던 곳을 찾고 거기부터 도는 식으로 풀었는데 이 문제는 그렇게 풀면 틀린다. 만약 순환(cycle)이 있을 경우 문제에서 요구하는 친구 관계가 있을지라도 이미 방문되었다고 표시되기 때문에 찾지 못하기 때문이다. 예를 들어 두 번째 예시의 경우 1에서 시작했을 때 1이 방문 체크가 되었기 때문에 1-0-3-2까지 밖에 못 돌아 count를 만족하지 못한다. 그러므로 visited 배열을 초기화 시키며 모든 경우를 돌면서 해당 관계가 있는지 찾아야 한다. 만약 찾았다면 return 시킨다.
[정답]
import java.io.*;
import java.util.*;
public class Main {
static ArrayList<Integer>[] A;
static boolean[] visited;
static boolean arrive;
public static void main(String[] args) throws IOException {
int n, m; // 노드, 에지 개수
arrive = false;
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
A = new ArrayList[n];
visited = new boolean[n];
for (int i = 0; i < n; i++)
A[i] = new ArrayList<Integer>();
for (int i = 0; i < m; i++) {
int s = sc.nextInt();
int e = sc.nextInt();
A[s].add(e);
A[e].add(s);
}
for (int i = 0; i < n; i++) {
DFS(i, 1); // depth 1부터 시작
if(arrive)
break;
}
if(arrive)
System.out.println("1");
else
System.out.println("0");
}
static void DFS(int now, int depth) {
if(depth == 5 || arrive) {
arrive = true;
return;
}
visited[now] = true;
for (int i : A[now]) {
if(!visited[i]){
DFS(i, depth+1);
}
}
visited[now] = false;
}
}
[원본]
import java.io.*;
import java.util.*;
public class Main {
static ArrayList<Integer>[] A;
static boolean[] visited;
static int n;
static int answer = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int m;
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
A = new ArrayList[n];
for (int i = 0; i < n; i++)
A[i] = new ArrayList<Integer>();
visited = new boolean[n];
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
A[a].add(b);
A[b].add(a);
}
for (int i = 0; i < n; i++) {
if(!visited[i]) {
visited[i] = true;
DFS(i, 1);
}
}
System.out.println(answer);
}
static void DFS(int person, int count) {
if(count == 5) {
answer = 1;
return;
}
visited[person] = true;
for (int i : A[person]) {
if(!visited[i]){
DFS(i, count+1);
}
}
}
}
[참고 자료]
- 알고리즘 코딩 테스트 자바편
'알고리즘 > Do it! 알고리즘 코딩 테스트' 카테고리의 다른 글
| 이진 탐색 (Binary Search) (0) | 2024.05.25 |
|---|---|
| 너비 우선 탐색 (BFS) (0) | 2024.05.24 |
| 기수 정렬 (Radix sort) (0) | 2024.05.21 |
| 병합 정렬 (Merge sort) (0) | 2024.05.21 |
| 퀵 정렬 (Quick sort) (0) | 2024.05.20 |
