DFS 기본 설명
DFS (Depth First Search, 깊이 우선 탐색)
DFS의 특징을 설명하자면 탐색을 한 방향으로 시작하면 갈 수 있는 최대한 깊게 간다. 그래서 위의 그래프를 예시로 하면 우선은 정점 1->2->4 들을 먼저 탐색할 것이다. 이다음으로는, 4에서 길이 막혔으므로 정점 2, 1로 되돌아가면서 다른 방향으로 탐색할 수 있는지 확인을 한다. 2에서는 다른 곳으로 갈 수 없고, 1에서 3 쪽으로 갈 수 있으므로 1->3->5 순으로 탐색을 할 것이다. 그리고 또 정점 3으로 돌아오면 6으로 갈 수 있으므로 6까지 탐색을 한다. 그러면 길이 또 막혔으므로 정점 3, 1 순으로 되돌아오면 더 이상 탐색할 수 있는 곳이 없으므로 탐색이 끝나는 것이다. 결과를 종합해보면 1->2->4->3->5->6 이다.
DFS의 특징들을 구사하려면 1.정점의 방문 여부 2.인접 여부를 확인할 행렬 3.재귀 함수를 구현할 줄 알아야 한다.
BFS 기본 설명
BFS (Breadth First Search, 너비 우선 탐색)
BFS의 특징을 설명하자면 층별로 탐색을 한다고 생각하면 된다. 위의 그래프를 예시로 하면 우선 정점 1이 베이스 노드면 1->2로 탐색을 할 것이다. 깊이 탐색하는 것이 아니라 베이스로부터 가까운 것을 먼저 탐색하므로 1로 돌아와 3을 탐색하게 되서 1->2->3 이 된다. 이렇게 층별로 탐색을 하니 결과는 뻔히 예상할 수 있다. 1->2->3->4->5->6 까지 탐색을 하면 탐색이 끝난다.
BFS의 특징들을 구사하려면 1.정점의 방문 여부 2.인접 여부를 확인할 행렬 3.큐를 구현할 줄 알아야 한다.
DFS 코드 구현
백준 1260번: DFS와 BFS 문제를 기준으로 DFS, BFS 코드 모두 따로 구현하겠다.
#include <stdio.h>
#define MAX 1001
int graph[MAX][MAX]={0,}; //인접행렬 만들때 사용
int visited[MAX]={0,}; // DFS 방문했는지 check
void DFS(int v, int N)
{
visited[v]=1; //방문한 곳: 1
printf("%d ", v); //정점 출력
for(int i=1; i<=N; i++)
{
if(graph[v][i] && !visited[i]) //2번: 인접여부 확인 && 1번: 정점의 방문 여부
DFS(i, N); //3번: 재귀 함수
}
}
int main(void)
{
int N,M,v; //정점개수,간선개수,시작정점
int x,y; //좌표
scanf("%d %d %d", &N, &M, &v);
//간선개수만큼 반복
while(M--)
{
scanf("%d %d", &x,&y);
//2번: 인접행렬 만들기
graph[x][y]=1;
graph[y][x]=1;
}
DFS(v, N);
return 0;
}
BFS 코드 구현
#include <stdio.h>
#define MAX 1001
int graph[MAX][MAX] = {0,}; // 인접행렬 만들때 사용
int visited[MAX] = {0,}; // BFS 방문했는지 check
int queue[MAX] = {0,};
void BFS(int v, int N)
{
int pop, front, rear;
front = rear = -1;
visited[v] = 1; //방문한 곳: 1
queue[++rear] = v; //3번: 큐->push
while(front < rear)
{
pop = queue[++front]; //3번: 큐->pop
printf("%d ",pop);
for(int i=1; i<=N; i++)
{
if(graph[pop][i] && !visited[i]) //2번: 인접여부 확인 && 1번: 정점의 방문 여부
{
visited[i] = 1;
queue[++rear] = i; //3번: 큐->push
}
}
}
}
int main(void)
{
int N,M,v; // 정점개수, 간선개수, 시작정점
int x,y; // 좌표
scanf("%d %d %d", &N, &M, &v);
//간선개수만큼 반복
while(M--)
{
scanf("%d %d", &x,&y);
//2번: 인접행렬 만들기
graph[x][y]=1;
graph[y][x]=1;
}
BFS(v, N);
return 0;
}