깊이 우선 탐색 (DFS)
깊이 우선 탐색은 그래프 완전 탐색 기법 중 하나이다.
그래프의 시작 노드에서 출발하여 탐색할 한쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다.
깊이 우선 탐색의 특징
스택이나 재귀 함수로 구현한다.
시간 복잡도
O(V + E)
V : 노드 수
E : 간선 수
DFS 문제를 풀어보기 전에 우선 그래프를 표현하는 방법부터 알아본다.
그래프 표현의 3가지 방법
그래프를 코드 상에 표현하는 방법은 크게 3가지가 있다.
에지 리스트(edge list)
에지 리스트는 에지를 중심으로 그래프를 표현한다.
에지 리스트는 배열에 출발 노드, 도착 노드를 저장하여 에지를 표현한다.
또는 출발 노드, 도착 노드, 가중치를 저장하여 가중치가 있는 에지를 표현한다.
에지 리스트로 가중치 없는 그래프 표현
가중치가 없는 그래프는 출발 노드와 도착 노드만 표현하기 때문에 배열의 열은 2개면 충분하다.
노드를 배열에 저장하여 에지를 표현하므로 에지 리스트라고 한다.
1에서 2로 가는 에지는 [1,2]로 표현한다.
0번째 열에 출발 노드, 1번째 열에는 도착 노드를 저장하면 그래프를 표현할 수 있다. 무방향 그래프의 경우에는 [1,2]와 [2,1]은 같은 에지일 것이다.
가중치가 필요하다면 열을 3개로 해서 마지막 열에 해당 에지의 가중치 정보를 저장하면 된다.
에지 리스트는 구현하기 쉽지만, 특정 노드와 관련된 에지를 탐색하기는 쉽지 않다.
에지 리스트는 노드 사이의 최단 거리를 구하는 벨만-포드나 최소 신장 트리를 찾는 크루스칼 알고리즘에 사용하며, 노드 중심 알고리즘에는 잘 사용하지 않는다.
인접 행렬(adjacency matrix)
인접 행렬은 2차원 배열을 자료구조로 이용하여 그래프를 표현한다.
에지 리스트와는 다르게 노드 중심으로 그래프를 표현한다.
인접 행렬에서 각 배열의 값은 가중치를 의미한다.
가중치가 없는 그래프라면 1로 표현한다.
1에서 2로 가는 에지를 인접 행렬은 1행 2열에 1을 저장하는 방식으로 표현한다.
인접 행렬을 이용한 그래프 구현은 쉽다.
두 노드를 연결하는 에지의 여부와 가중치값은 배열에 직접 접근하면 바로 확인할 수 있다는 장점이 있다.
하지만 노드와 관련되어 있는 에지를 탐색하려면 N번 접근해야 하므로 시간 복잡도가 인접 리스트에 비해 느리고 노드 개수에 비해 에지가 적을 때는 공간 효율성이 떨어진다.
인접 리스트(adjacency list)
C++의 인접 리스트는 이차원 벡터로 그래프를 표현한다.
자료형은 문제의 조건에 맞게 설정한다.
다른 방법에 비해 인접 리스트로 그래프를 표현하는 것은 복잡하다.
하지만 노드와 연결된 에지를 탐색하는 시간은 매우 뛰어나며, 노드 개수가 커도 공간 효율성이 좋아서 메모리 초과 에러도 발생하지 않는다.
이러한 장점으로 인해 실제 코딩 테스트에서는 인접 리스트를 이용한 그래프 구현을 선호한다.
DFS로 돌아와서
DFS는 재귀함수를 이용하므로 스택 오버 플로에 유의해야 한다.
DFS를 응용해서 풀 수 있는 문제는 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 등이 있다.
DFS의 핵심 이론
DFS는 한 번 방문한 노드는 다시 방문하면 안 되므로 노드 방문 여부를 체크할 배열이 필요하다.
1. DFS를 시작할 노드를 정한 후 사용할 자료구조 초기화 하기
DFS를 위해 필요한 초기 작업은 인접 리스트로 그래프 표현하기, 방문 배열 초기화하기, 시작 노드 스택에 삽입하기가 있다.
시작 노드를 스택에 삽입함과 동시에 방문 배열에 방문 표시를 해준다.
2. 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입한다.
3. 스택 자료구조에 값이 없을 때까지 반복한다.
앞의 1,2 작업을 스택 자료구조에 값이 없을 때까지 반복한다.
이 때, 한 번 방문한 노드는 방문 배열을 참고해서 스택에 다시 삽입하지 않는 것이 핵심이다.
백준 11724번 문제
https://www.acmicpc.net/problem/11724
#include <iostream>
#include <vector>
using namespace std;
static vector<vector<int>> graph;
static vector<bool> visited;
void DFS(int v);
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int v, e;
cin >> v >> e;
graph.resize(v + 1);
visited = vector<bool>(v + 1, false);
//간선 개수만큼 인접 리스트에 간선 정보 추가
for (int i = 0; i < e; i++)
{
int start, end;
cin >> start >> end;
graph[start].push_back(end);
graph[end].push_back(start);
}
int answer = 0;
//시작 노드 넣기
for (int i = 1; i < v + 1; i++)
{
//방문하지 않은 노드라면 시작 노드로 넣고 DFS를 시작한다.
if (!visited[i])
{
answer++;
DFS(i);
}
}
cout << answer;
return 0;
}
void DFS(int v)
{
//방문 했으니 그냥 리턴
if (visited[v])
{
return;
}
//방문 표시
visited[v] = true;
//인접 리스트의 노드들 방문
for (int i : graph[v])
{
//방문하지 않은 것만 방문
if (visited[i] == false)
{
DFS(i);
}
}
}
방문하지 않는 노드를 시작 노드로 해서 여러 번 DFS를 해서 연결된 노드의 개수를 구하면 되는 문제였다.
그래프를 표현하고 그래프 탐색 알고리즘을 짤 수 있다면 풀 수 있는 문제이다.
백준 2023번 문제
https://www.acmicpc.net/problem/2023
#include <iostream>
#include <vector>
using namespace std;
void DFS(int num, int j);
bool isPrime(int num);
static int N;
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N;
// 2, 3, 5, 7로 시작
// 그 뒤는 무조건 홀수만 소수의 가능성이 있다.
DFS(2, 1);
DFS(3, 1);
DFS(5, 1);
DFS(7, 1);
return 0;
}
void DFS(int num, int j)
{
if (j == N)
{
if (isPrime(num))
{
cout << num << '\n';
return;
}
}
for (int i = 0; i < 10; i++)
{
//짝수 가지치기
if (i % 2 == 0)
continue;
if (isPrime(num * 10 + i))
DFS(num * 10 + i, j + 1);
}
}
bool isPrime(int num)
{
if (num < 1) return false;
if (num == 2) return true;
if (num % 2 == 0) return false;
for (int i = 3; i <= num / 2; i++)
{
if (num % i == 0)
return false;
}
return true;
}
이 문제는 혼자 못 풀었는데 그 이유는 DFS 문제인데 그래프를 표현할 필요가 없어서 DFS는 그래프랑 같이 쓰는 느낌이라고 생각해서 DFS를 어떻게 적용해야할지 감이 안 왔기 때문이다.
이 문제에서 DFS를 써야하는 당위는 오름차순으로 신기한 소수를 출력해야 하기 때문인 것 같다. 0부터 탐색을 시작해서 DFS를 돌면 제일 작은 수 부터 출력하게 되고 모든 경우를 탐색할 수 있다.
중간에 문제에 알맞게 가지치기를 해서 필요없는 연산을 줄였다.
백준 13023번 문제
https://www.acmicpc.net/problem/13023
#include <iostream>
#include <vector>
using namespace std;
static int N;
static int M;
static vector<vector<int>> graph;
static vector<bool> visited;
void DFS(int v, int depth);
bool answer = false;
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N >> M;
graph.resize(N);
visited = vector<bool>(N, false);
//인접 리스트 셋팅
for (int i = 0; i < M; i++)
{
int a, b;
cin >> a >> b;
graph[a].push_back(b);
graph[b].push_back(a);
}
for (int i = 0; i < N; i++)
{
DFS(i, 1);
if (answer == true)
break;
}
cout << (int)answer;
return 0;
}
void DFS(int v, int depth)
{
if (visited[v])
{
return;
}
//방문 체크
visited[v] = true;
if (depth >= 5)
{
answer = true;
return;
}
for (int i : graph[v])
{
if (!visited[i])
{
DFS(i, depth + 1);
}
}
//다른 노드를 시작으로 다시 반복해야 하니까 false로 바꿔준다.
visited[v] = false;
}이 문제는 맨 밑에 visited[v] = false;를 깜박해서 틀렸다.
우선 이 문제의 핵심은 DFS의 깊이가 5인 탐색이 존재하는지이다.
이를 탐색하려면 모든 노드를 시작으로 해서 각각 DFS를 해야하는데
한 번 돌고나서 방문 배열을 초기화하지 않아서 틀렸다.
여러 번 돌아야 할 때는 방문 배열을 잊지말고 되돌려주자.
공부 자료 : Do it! 알고리즘 코딩 테스트 (김종관, 이지스퍼블리싱)
