그래프를 방문하거나 탐색하는 방법은 여러 가지가 있다. 오늘은 그중 대표적으로 쓰이는 DFS와 BFS에 대해 알아보려고 한다.
01. DFS(Depth First Search)
DFS는 주로 완전 탐색이나 백트래킹과 같이 탐색의 횟수, 즉 그래프의 최대 경로가 정해져 있거나 예측 가능한 경우에 주로 이용한다. DFS는 BFS와 유사하지만 선택한 정점을 저장하기 위한 도구로 큐(Queue) 대신 스택(Stack)을 이용한다는 점에서 BFS와 차이를 보인다. 이때 스택을 직접 사용하지 않고 주로 스택의 원리를 이용하는 재귀 함수를 통해 구현하는 편이다.
DFS는 다음과 같은 절차로 탐색을 진행한다.
- 선택한 정점에서 해야 할 작업을 진행한다.
- 선택한 정점과 연결된 정점 중 아직 방문하지 않은 정점을 방문한다.
- 만약 더는 방문할 정점이 없다면 이전 정점으로 되돌아간다.
- 위의 과정을 반복한다.
02. BFS(Breadth First Search)
BFS는 최단거리, 최소 비용과 같이 최솟값과 관련된 문제를 해결할 수 있는데, 이때 그래프의 가중치(시간, 비용, 거리 등)가 1이어야만 합니다. 유한한 범위여야만 사용이 가능한 BFS와는 달리 BFS는 모든 경로에 대한 동시 탐색이 가능하여 최대 경로를 몰라도 사용할 수 있다는 장점이 있어, 최단 거리, 최소 비용 등을 구할 수 있습니다.
BFS는 다음과 같은 절차로 탐색을 진행한다.
- 저장된 정점 중 첫 번째 정점을 선택하여 저장된 정점에서 제거
- 제거한 정점에서 해야 할 작업 진행
- 제거한 정점과 연결된 정점 중 방문하지 않은 모든 정점 저장(2번과 3번은 순서가 바뀌어도 상관없다)
- 저장된 정점에 모든 노드가 제거될 때까지 1~3번 과정 반복
백준 2606 바이러스 문제로 DFS, BFS비교해보려고 한다. 문제는 1번이 바이러스 걸렸을 때 1번과 연결된 부분이 모두 바이러스 걸리게 되는데 그 갯수를 묻는 것이다.
우선, DFS로 구현해보겠다.
#include<stdio.h>
int visited[101] = { 0 };
int virus[101][101] = { 0 };
int count;
int N;
void dfs(int start) {
if (visited[start] == 1)return;
visited[start] = 1;
count++;
for (int i = 1; i <= N; i++) {
if (virus[start][i]) {
dfs(i);
}
}
}
int main() {
int i;
int start;
int line;
int a, b;
scanf("%d", &N);
scanf("%d", &line);
count = 0;
for (i = 0; i < line; i++) {
scanf("%d %d", &a, &b);
virus[a][b] = 1;
virus[b][a] = 1;
}
dfs(1);
if (count == 0)count++;
printf("%d\n", count - 1);
}
다음은 BFS를 사용한것이다.
#include<iostream>
#include<queue>
#include<stdio.h>
using namespace std;
int visited[101] = { 0 };
int virus[101][101] = { 0 };
int N;
int main() {
queue<int> q;
int i;
int start;
int line;
int a, b;
int count;
count = 0;
scanf("%d", &N);
scanf("%d", &line);
for (i = 0; i < line; i++) {
scanf("%d %d", &a, &b);
virus[a][b] = 1;
virus[b][a] = 1;
}
q.push(1);
visited[1] = 1;
while (!q.empty()) {
start = q.front();
q.pop();
for (i = 0; i <= N; i++) {
if (virus[start][i] == 1 && visited[i] == 0) {
q.push(i);
visited[i] = 1;
count++;
}
}
}
printf("%d\n", count);
}
DFS는 스택을 사용할 필요없이 재귀만 사용하면 되기 때문에 C언어로만 구현하였다. BFS는 큐를 사용해야 하기에 C++의 queue라이브러리를 이용하여 구현하였다.
03. 백트래킹
백트래킹은 DFS를 기본 토대로 가진다 DFS를 하다보면 굉장히 비효율적인 상황을 마주하곤 한다. 굳이 가지 않아도 될 곳을 방문하는 경우를 DFS에서는 자주 접할 때가 있다. 이런 상황에서 백트래킹은 비효율적인 경로를 차단하고 목표지점에 갈 수 있는 가능성이 있는 길을 검사하는 방법이다. 백트래킹은 DFS에 가지치기(Pruning)을 통해 가지 않아도 될 부분을 탐색한다. 상황에 따라서는 굉장히 효율적인 방법이다.
백트래킹의 일반적인 알고리즘은 다음과 같다.
void checknode(node v)
{
node u;
if(promising(v))
if(there is a solution at v)
write the solution;
else
for(each child u of v)
checknode(u);
}다음은 백준 9663번 문제인 N-Queen 문제이다.
백트래킹의 대표적인 N-Queen 문제는 크기가 N x N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
예를 들어 N이 4라고 하면,
위와 같이 2개의 방법이 있다.
위와 같이 dfs 방식으로 가지를 치는데, 백트래킹은 전도유망(promising)성을 검사해 가지치기를 해야 한다.
퀸의 규칙인 직선과 대각선을 피하게 되면 위 x표 쳐져 있는 부분과 같이 가지를 쳐낸다. 그럼 그 쪽으로 갈 필요없이 2,3부터 탐색을 하면 되는 것이다.
코드를 살펴보자.
N-queen을 풀 때 유의해야 할 부분은 세가지이다.
첫번째는 시작점.
int main() {
int row;
row = -1;
scanf("%d", &N);
Nqueen(row);
printf("%d\n", count);
}시작점은 다양하다. -1로 설정할 수 있고 0으로 설정할 수도 있다. 각자 풀 기 편한대로 하면된다. 하지만 시작점을 유의하며 다음 코딩을 생각해야 좋다.
두번째는 재귀부분.
void Nqueen(int row)
{
if (Nqueen_Promising(row)) {
if (row == N - 1) {
count++;
}
else {
for (int i = 0; i < N; i++) {
q[row + 1] = i;
Nqueen(row + 1);
}
}
}
}나같은 경우에는 처음부터 전도 유망성 여부를 검사해줬다.(Nqueen_Promising(row)). 위와 같은 경우 재귀 영역을 생성한 후 전도 유망성을 검사한다. 그러나 더 효율적으로 하기 위해서는 굳이 재귀 영역을 생성하기 전에 전도 유망성을 검사해주는 방법이 있다.
void Nqueen(int row)
{
if(row == N)
count += 1;
else
{
for(int i=0;i<N;i++)
{
q[row] = i;
if(Nqueen_Promising(row))
Nqueen(row+1);
}
}
}promising을 밑으로 빼줌으로서 시간을 단축하였다.
