[DFS] 깊이 우선 탐색 (Depth First Search)

깊이 우선 탐색 (Depth First Search)

 

탐색알고리즘으로는     깊이 우선 탐색(DFS : Depth First Search)과 

  너비 우선 탐색(BFS : Breath First Search)이 있다.

깊이 우선 탐색(이하 DFS)은 일반적으로 구현할 때는 스택(stack)을 이용하고,

트리나 그래프 같은 자료구조에서 데이터를 탐색할 때 사용하는 알고리즘이다.

DFS 알고리즘은 더이상 나아갈 길이 보이지 않을 만큼 깊이 찾아가면서 탐색한다.

만약, 나아갈 길이 존재하지 않으면 이전의 위치로 돌아와 찾아가지 않은 다른 길로 뻗어 나가면서 탐색해 나간다.

 

그래프를 보면 숫자가 있는 원은 정점(Vertex)라고 하고, 정점과 정점을 잇는 연결선을 간선(Edge)이라고 한다.

이제 위 그래프를 DFS를 이용하여 탐색해 보자.

 

맨 위의 정점인 1을 head로 찾아 내려갈 때, 순서는 1->2->4->8->5->6->3->7(->8 끝) 이렇게 돌면서 찾아간다.

 

설명을 하자면

1) 1과 연결된 정점이 2와 3이 있는데 우선 2를 먼저 찾아간다.

2) 2정점에서는 4와 5중에서 4를 먼저 찾아간다.

3) 4에서는 2와 8이 연결되어 있지만 2는 이전 정점이므로 8로 이동

4) 8에서는 4, 5, 6, 7 연결되어 있으며 4는 이전노드 이므로 5로 이동

5) 5는 2와 8중에서 둘 다 이미 탐색한 곳이므로 더이상 나아가지 않고 8로 되돌아 온다

6) 되돌아온 8에서 새로운 정점인 6으로 이동

7) 6에서는 3으로 이동

8) 3에서 7로 이동

9) 7에서는 3과 8 이미 탐색한 곳이므로 종료

 

 

DFS를 구현하기 전에 정점과 정점의 연결 관계를 인접 행렬로 표현한다.

다른 방법도 있는 것 같으나 참고한 블로그에서는 그래프 입력을 인접 행렬로 받았다. 항상 그냥 입력자체를 배열로 받았는데 이와 같이 연결자체로 받고 인접 관계를 알 수 있어서 DFS보다 인접 행렬 자체가 더 도움이 된 것 같다. 

 

 

 

정점의 개수만큼 2차원 배열을 만들고 연결된 정점들을 예를들어 1과 2, 3이 연결되어 있으므로

(1, 2), (1, 3)에 1을 넣고 연결되지 않은 (1, 4)와 자기 자신인 (1, 1)은 0을 넣는다.

이렇게 나아가면 인접 행렬은 대각선을 기준으로 대칭이 되는데 입력 받을 때 중복되지 않게

입력할 수도 있으니 처음 입력받을 때 [i][j]와 [j][i]에 한번에 1을 넣으면 된다.

 

 

그럼 그림 1의 그래프를 탐색하는 DFS알고리즘을 구현해 보자.

입력은 정점의 개수와 시작 정점 그리고 연결된 정점들을 입력으로 받는다.

-1과 -1이 입력되면 정점 입력을 중단하기로 한다.

 

입력 : 8 1

   1 2 1 3 2 4 2 5 4 8 5 8 3 6 3 7 6 8 7 8 -1 -1

 

출력 : 1에서 2로 이동

   2에서 4로 이동

   4에서 8로 이동

   8에서 5로 이동

   8에서 6로 이동

   6에서 3로 이동

   3에서 7로 이동

   

 

#include <stdio.h>
 
int n;
int map[30][30], visit[30];
 
void DFS(int v)
{
    int i;
 
    visit[v] = 1;
    for (i = 1; i <= n; i++)    {
        if (map[v][i] == 1 && !visit[i])    {
            printf("%d에서 %d로 이동\n", v, i);
 
            DFS(i);        // 재귀 !        재귀라서 나아갈 곳이 없으면 다시 돌아온다.
        }
    }
}
 
int main(void)
{
    int start;
    int v1, v2;
 
    scanf("%d%d", &n, &start);
 
    while (1)
    {
        scanf("%d%d", &v1, &v2);
        if (v1 == -1 && v2 == -1)    {
            break;
        }
        map[v1][v2] = map[v2][v1] = 1;
    }
 
    DFS(start);
 
    return 0;
}

 

 

재귀를 이용하여 스택으로 구현하였다.

지금까지 재귀를 이용해서 풀은 알고리즘 문제가 BFS 라고 생각하면서 문제를 풀은 거였는데,

DFS 에서 '찾지 못하면 되돌아간다' 라는 부분을 구현하지 못해서 DFS를 못만든다고 생각했는데

이번에 참고 블로그에 있는 코드를 보고 재귀를 다시 그려본 결과

재귀를 이용하여 푸는 탐색 알고리즘은 스택이었고 DFS였다!!

 

오히려 Queue를 이용하는 BFS를 못푸는 것이었다는걸 이번에 알게되었다.

이런 바보같은ㅋㅋㅋㅋ

그렇담 다음에는 BFS 알고리즘을 공부해 보아야 겠다.

 

[참고] http://blog.eairship.kr/268

 

이 블로그의 알고리즘 설명이 제일 이해하기 쉬운 것 같다.

앞으로 BFS나  Circular Queue, Heap 같은 자료구조 및 알고리즘 공부할 때 자주 찾아들어갈 것 같다.