깊이 우선 탐색, DFS 이란?
DFS 란 트리에서 생각해보면 트리를 탐색할 때 시작 정점에서 한 방향으로 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 다른 방향으로 다시 탐색을 진행하는 방법과 매우 유사합니다. 즉 DFS는 특정 노드에서 시작해 다음 분기로 넘어가기 전에 해당 분기를 완전히 탐색하는 방법입니다. DFS 는 스택을 사용해 구현합니다.
아래의 동작과 구현에서 확인하겠지만, 깊이 우선 탐색을 통해 그래프를 탐색하게 되면 모든 간선을 조사하므로 정점의 수가 n 이고 간선의 수가 e인 그래프인 경우, 그래프가 인접 행렬로 표시되어 있다면 O(n^2), 인접 리스트로 표현되어 있는 경우는 O(n+e) 가 됩니다. 따라서 희소 그래프인 경우는 DFS는 인접 리스트의 사용이 인접 행렬보다 시간적으로 유리합니다.
DFS 진행 과정
먼저 DFS 의 동작을 이해하기 위해 진행 과정을 자세히 살펴보도록 하겠습니다.
위 같은 트리 구조가 있을 때 스택을 하나 선언합니다. 스택에는 방문한 정점들을 삽입하게 되고, 더 이상 진행할 수 없을 경우 pop 을 통해 돌아오는 역할을 하게 됩니다. 또한 위 그림에는 나와있지 않지만 방문한 정점들을 표시하기 위해 일반적으로 visited 배열을 선언하게 되는데요, 이는 아래의 구현 단계에서 다시 확인해보도록 하고 이번에는 동작에 집중해서 이해를 먼저 해봅시다. 파란색은 아직 방문하지 않은 정점이고, 방문한 정점은 주황색으로 나타납니다.
먼저 루트 노드부터 DFS를 시작합니다. 루트 노드를 방문하고 방문한 노드를 스택에 push 합니다.
이후 스택의 top 부분에 있는 A 노드의 인접 노드인 B를 방문하고, 스택에 B노드를 추가합니다. 이 때 C 노드를 먼저 방문해도 되고, 순서는 상관이 없습니다.
스택의 top에 있는 B 노드의 인접 노드인 D 노드를 방문하고 스택에 D 노드를 push 합니다.
여기서 D 노드에는 인접 노드가 없기 때문에 스택에서 D 를 제거합니다. 이는 다시 B 정점으로 돌아가는 것과 같습니다.
이 후 다시 스택의 top 에 있는 B에서 인접한 노드인 E를 방문하고 E를 push 합니다.
이 후 E 노드에는 더 이상 방문할 노드가 없으므로 pop 을 통해 B로 돌아가고, B에서도 이미 다 방문한 노드밖에 없으므로 다시 pop 을 통해 A까지 돌아가게 됩니다.
이제 오른쪽을 방문해야 겠죠. 왼쪽과 동일한 과정으로 진행됩니다.
C를 방문하고 C를 스택에 push, 그 이후 인접 노드인 F 노드를 방문해서 stack에 push 하고
F 노드에서는 더 이상 방문할 정점이 없으므로 pop 연산을 통해 C로 돌아갑니다.
G까지 방문이 끝나면 끝난것이 아니죠. G에서 다시 갈 노드가 있는지 탐색을 하고 없기 때문에 pop 을 통해 C로 돌아가고, C에서도 탐색을 진행하지만 모두 방문했기 때문에 갈 곳이 없어서 pop을 통해 A로 돌아가고. 이 연산을 계속 진행합니다.
결국 모든 정점을 방문하고 나면 스택에는 아무 데이터도 남아있지 않습니다. 이렇게 되면 DFS를 통한 트리의 탐색이 완료됩니다.
DFS 의 장단점
DFS 장점
- 현재 경로상의 노드들만 기억하면 되므로 저장 공간의 수요가 비교적 적다.
- 목표 노드가 깊은 단계에 있는 경우 해를 빨리 구할 수 있다.
- BFS 보다 구현이 간단하다.
DFS 단점
- 단순 검색 속도가 BFS 보다 느리다.
- 해가 없는 경우에 빠질 수 있다. 따라서 사전에 탐색할 임의의 깊이를 지정할 필요가 있다.
- DFS는 해를 구하면 탐색이 종료된다. 따라서 구한 해가 최적해가 아닐 수 있다.
DFS 구현
DFS를 구현하는 방법은 2가지가 있습니다. 위에서 확인했던 것처럼 스택 자료구조를 이용해 구현하거나 재귀를 통해 구현할 수도 있습니다. C언어는 스택 자료구조형을 C++에서 처럼 STL로 지원하거나 파이썬처럼 list 를 사용할 수 없기 때문에 스택을 먼저 구현한 이후에 DFS를 구현해야 합니다. 먼저 재귀를 통해 구현해보고, 그 이후 스택을 사용해 DFS를 구현해보겠습니다. 또한 인접 행렬로 그래프를 표현할 때와 인접 리스트를 통해 그래프를 표현할 때 DFS의 형태가 다릅니다.
인접 행렬 DFS (재귀)
// 인접 행렬로 표현된 그래프에 대한 깊이 우선 탐색
void dfs_mat(GraphType* g, int v)
{
int w;
visited[v] = TRUE; // 정점 v의 방문 표시
printf("정점 %d -> ", v); // 방문한 정점 출력
for (w = 0; w<g->n; w++) // 인접 정점 탐색
if (g->adj_mat[v][w] && !visited[w])
dfs_mat(g, w); //정점 w에서 DFS 새로 시작
}재귀로 나타낸 DFS는 간단합니다. 그래프와 시작점을 입력으로 받게 되고, 시작점은 루트 노드를 넣어줍니다.
visited 배열을 통해 방문한 정점을 True로 바꿔줍니다. 전체코드에서 보면 알겠지만 visited 배열은 맨 처음 전부 False 로 초기화 시켜주고, 방문한 경우에만 True로 바꿔줘서 visited 배열 전체가 True 인경우 dfs를 종료합니다.
그래프 타입 g에는 정점의 개수를 나타내는 n이 있습니다. 즉 모든 정점에 대해서 첫번째 for문이 반복됩니다.
그 다음 if 문을 통해 visited 배열의 값이 Flase 이면서, 인접 행렬의 값이 1인 경우, 즉 간선이 있고 방문하지 않은 노드인 경우에만 다시 dfs를 재귀적으로 호출하는 겁니다. if 문을 통과하면 다음 노드로 이동한다고 생각하셔도 무방합니다.
+ 파이썬을 사용한 재귀 DFS 코드
# DFS 메서드 정의
def dfs(graph, v, visited):
# 현재 노드를 방문 처리
visited[v] = True
print(v, end=' ')
# 현재 노드와 연결된 다른 노드를 재귀적으로 방문
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)
인접 행렬 DFS (재귀) 전체 코드
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define MAX_VERTICES 50
typedef struct GraphType {
int n; // 정점의 개수
int adj_mat[MAX_VERTICES][MAX_VERTICES];
} GraphType;
int visited[MAX_VERTICES];
// 그래프 초기화
void init(GraphType* g)
{
int r, c;
g->n = 0;
for (r = 0; r < MAX_VERTICES; r++)
for (c = 0; c < MAX_VERTICES; c++)
g->adj_mat[r][c] = 0;
}
// 정점 삽입 연산
void insert_vertex(GraphType* g, int v)
{
if (((g->n) + 1) > MAX_VERTICES) {
fprintf(stderr, "그래프: 정점의 개수 초과");
return;
}
g->n++;
}
// 간선 삽입 연산
void insert_edge(GraphType* g, int start, int end)
{
if (start >= g->n || end >= g->n) {
fprintf(stderr, "그래프: 정점 번호 오류");
return;
}
g->adj_mat[start][end] = 1;
g->adj_mat[end][start] = 1;
}
// 인접 행렬로 표현된 그래프에 대한 깊이 우선 탐색
void dfs_mat(GraphType* g, int v)
{
int w;
visited[v] = TRUE; // 정점 v의 방문 표시
printf("%d ", v); // 방문한 정점 출력
for (w = 0; w < g->n; w++) // 인접 정점 탐색
if (g->adj_mat[v][w] && !visited[w])
dfs_mat(g, w); //정점 w에서 DFS 새로 시작
}
int main(void)
{
GraphType* g;
g = (GraphType*)malloc(sizeof(GraphType));
init(g);
for (int i = 0; i < 4; i++)
insert_vertex(g, i);
insert_edge(g, 0, 1);
insert_edge(g, 0, 2);
insert_edge(g, 0, 3);
insert_edge(g, 1, 2);
insert_edge(g, 2, 3);
printf("깊이 우선 탐색\n");
printf("DFS 순서: ");
dfs_mat(g, 0);
printf("\n");
free(g);
return 0;
}
인접 행렬 DFS (스택)
// DFS 함수
void dfs_mat(GraphType* g, int start) {
Stack stack;
init(&stack);
push(&stack, start);
visited[start] = 1;
printf("DFS 순서: ");
printf("%d ", start);
while (!isEmpty(&stack)) {
int current = pop(&stack);
for (int i = 0; i < g->n; i++) {
if (g->adj_mat[current][i] == 1 && visited[i] == 0) {
printf("%d ", i);
push(&stack, i);
visited[i] = 1;
}
}
}
}재귀로 구현한 dfs랑 출력 순서를 맞추려고 push 부분에서 출력을 하도록 한 스택구현 DFS 입니다. 맨 위의 동작 원리를 스택으로 설명했기 때문에 먼저 보고 온 이후에 코드를 순서대로 따라가시면 어렵지 않게 따라갈 수 있습니다.
인접 행렬 DFS (스택)
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define MAX_VERTICES 50
#define MAX_SIZE 100
typedef struct GraphType {
int n; // 정점의 개수
int adj_mat[MAX_VERTICES][MAX_VERTICES];
} GraphType;
int visited[MAX_VERTICES];
// 그래프 초기화
void init(GraphType* g)
{
int r, c;
g->n = 0;
for (r = 0; r < MAX_VERTICES; r++)
for (c = 0; c < MAX_VERTICES; c++)
g->adj_mat[r][c] = 0;
}
// 정점 삽입 연산
void insert_vertex(GraphType* g, int v)
{
if (((g->n) + 1) > MAX_VERTICES) {
fprintf(stderr, "그래프: 정점의 개수 초과");
return;
}
g->n++;
}
// 간선 삽입 연산
void insert_edge(GraphType* g, int start, int end)
{
if (start >= g->n || end >= g->n) {
fprintf(stderr, "그래프: 정점 번호 오류");
return;
}
g->adj_mat[start][end] = 1;
g->adj_mat[end][start] = 1;
}
// 스택 정의
typedef struct {
int data[MAX_SIZE];
int top;
} Stack;
// 스택 초기화
void init(Stack* stack) {
stack->top = -1;
}
// 스택이 비어있는지 확인
bool isEmpty(Stack* stack) {
return stack->top == -1;
}
// 스택에 데이터 추가
void push(Stack* stack, int value) {
if (stack->top >= MAX_SIZE - 1) {
printf("Stack Overflow\n");
return;
}
stack->data[++(stack->top)] = value;
}
// 스택에서 데이터 제거 및 반환
int pop(Stack* stack) {
if (isEmpty(stack)) {
printf("Stack Underflow\n");
return -1;
}
return stack->data[(stack->top)--];
}
// DFS 함수
void dfs_mat(GraphType* g, int start) {
Stack stack;
init(&stack);
push(&stack, start);
visited[start] = 1;
printf("DFS 순서: ");
printf("%d ", start);
while (!isEmpty(&stack)) {
int current = pop(&stack);
for (int i = 0; i < g->n; i++) {
if (g->adj_mat[current][i] == 1 && visited[i] == 0) {
printf("%d ", i);
push(&stack, i);
visited[i] = 1;
}
}
}
}
int main(void)
{
GraphType* g;
g = (GraphType*)malloc(sizeof(GraphType));
init(g);
for (int i = 0; i < 4; i++)
insert_vertex(g, i);
insert_edge(g, 0, 1);
insert_edge(g, 0, 2);
insert_edge(g, 0, 3);
insert_edge(g, 1, 2);
insert_edge(g, 2, 3);
printf("깊이 우선 탐색\n");
dfs_mat(g, 0);
printf("\n");
free(g);
return 0;
}
스택 구현 코드와 인접행렬 그래프 코드가 긴거지 DFS 코드는 실제로 굉장히 짧습니다. 동작만 이해한다면 10줄 내외로 짤 수 있는 코드가 DFS이기 때문에 꼭 동작을 이해하고 재귀로도, 스택으로도 이를 구현하는 방법을 익혀봅시다. 감사합니다.
인접 리스트로 표현된 그래프에서의 DFS는 아래 포스팅에 나와 있습니다.
[C 자료구조] 인접 리스트 그래프 탐색 ( DFS, BFS )
[C 자료구조] 그래프 ADT 구현 : 인접행렬 / 인접리스트 n = 0; for (row = 0; row < MAX_VERTICES; row++) for (col = 0; col < MAX_VERTICES; col++) g->adj_mat[row][col] = 0; } Graph 구조체 안에는 인접 행렬을 나타낼 2차원 배열
songsite123.tistory.com
참고 :
https://code-lab1.tistory.com/
C언어로 쉽게 풀어쓴 자료구조 - 생능출판
'알고리즘' 카테고리의 다른 글
| [알고리즘] BFS (너비 우선 탐색) (0) | 2023.05.28 |
|---|