안녕하세요. 김용성입니다. 오늘부터 드디어 DFS와 BFS에 대해 포스팅을 하게 되었네요...
제가 집중력이 부족해서인지, 아니면 좀 이해력이 좋지 않은 건지 잘 모르겠지만, 아무튼 저는 이해하는데에 시간이 좀 걸렸던 것 같아요.

내용이 조금 많아 이번 포스팅에서는 그래프의 탐색에 대한 설명을 드린 뒤, DFS를 구현해보는 시간을 가지도록 하겠습니다.

설명 시작하도록 하겠습니다!

그래프의 탐색

정의

그래프의 꽃은 뭐니뭐니해도 탐색! 이라고 제가 이전 포스팅에서도 언급했었는데요. '탐색' 이라는 단어의 뜻은 다들 아실테니 다들 그래프의 탐색이 어떤식으로 동작을 할지에 대해서는 막연하게나마 유추를 하실 수 있을겁니다.

그래프의 탐색은 다음과 같이 정의할 수 있습니다.

하나의 정점에서 간선을 따라 다른 정점들을 한번씩 방문하는 행위

이러한 탐색을 통해서 우리가 얻을 수 있는 것은 무엇일까요?

특정 정점에서 다른 정점으로 간선을 따라 이동이 가능한지 그래프 탐색을 통해 확인 가능

예로 미로 탐색을 들 수가 있겠네요!

종류

이러한 그래프의 탐색은 두가지의 종류가 있습니다. 하나는 깊이 우선 탐색인 DFS이고, 다른 하나는 너비 우선 탐색인 BFS 입니다. 이번 포스팅에서는 DFS에 대해서만 다루고, 다음 포스팅에서 BFS를 다루도록 하겠습니다.

전공자분들이라면 한번 쯤은 들어보셨을 것이라 생각하고, 비전공자분들이여도 만약 개발자로 전향하시길 원하신다면 이 개념은 반드시 알고 넘어가는 것이 좋습니다. 어느 기업이든 코딩테스트 문제에 DFS/BFS 관련 문제는 꼭 한문제 이상 출제가 되기 때문입니다.

언급한 두 방식에 대해 상세히 설명하고 구현하기에 앞서, 개략적인 설명을 통해 여러분들의 이해를 돕도록 하겠습니다.

DFS

DFS에서는 '한 우물'이라는 단어를 접목시키면 이해하기 좋습니다. 트리도 그래프의 일종이기 때문에 보다 직관적인 설명을 위해 저는 트리를 활용하도록 하겠습니다.

자 그림을 한번 보겠습니다.
탐색 순서는 0->1->3->2->5->6입니다.
어떻게 이런 탐색순서가 생겼는지 한번 살펴볼까요?
0번에서 탐색을 시작할 경우 0->1->3으로 한 방향 탐색을 계속합니다. 그 이후에 더 탐색할 곳이 없으면 바로 그 옆에 있는 4번을 탐색합니다. 그 이후에 1이란 서브트리에는 더이상 탐색할 곳이 없는데요. 그렇게 탐색을 마치면 2번 서브트리를 탐색하는 것이죠. 그 이후에는 5번, 6번 순서로 탐색을 합니다. 제가 '한우물'이라고 이야기한 것은 이러한 탐색 방식 때문입니다. '깊이'라는 용어에서 알 수 있듯, '한 우물'로 깊게 탐색을 마치면 그 옆 우물, 그 옆 우물을 탐색한다고 보시면 이해하기 쉬워요.

이제 DFS 탐색법에 대해 보다 깊이 있게 살펴보도록 하겠습니다:)

DFS

깊이 우선 탐색의 경우, 기본적으로 재귀호출을 사용한다고 생각하시면 됩니다. 제가 그 이유를 설명드리도록 하겠습니다.

위 그림을 다시한번 살펴보겠습니다.

순환 과정

1, 0번 정점에 대한 탐색을 수행합니다.
2, 1번 정점에 대한 탐색을 수행합니다.
3, 3번 정점에 대한 탐색을 수행합니다.
4, 3번 정점에서 더 탐색할 것이 없으므로, 1번 정점에 대한 탐색을 계속해서 진행합니다.
5, 4번 정점에 대한 탐색을 수행합니다.
6, 4번 정점에 대해 더 탐색할 것이 없고, 1번 정점에 대해서도 더이상 탐색을 진행할 것이 없습니다. 0번 정점에 대한 탐색을 계속해서 진행합니다.
7, 2번 정점에 대한 탐색을 수행합니다.
8, 5번 정점에 대한 탐색을 수행합니다.
9, 5번 정점에서 더 탐색할 것이 없으므로, 2번 정점에 대한 탐색을 계속해서 진행합니다.
10, 6번 정점에 대한 탐색을 수행합니다.
11, 탐색을 마쳤습니다.

탐색의 과정은 이렇습니다. 큰 문제를 작게 쪼개서 계속해서 파고드는 방식, 즉 재귀함수를 사용할 수 있는 대표적인 상황이죠. 또한 재귀함수를 사용하는 문제이기에 스택을 사용할 수 있습니다.
스택은 LIFO성질을 가지고 있죠?
빈 스택에 정점들을 담는다면 다음과 같은 순서가 성립될 것입니다. (쉬운 설명을 위해 오른쪽 자식 노드부터 스택에 담긴다고 가정하겠습니다.)

탐색 순서에 따른 스택의 변화

[] //빈 스택
[0] //0번 탐색
[2,1] //0번 탐색 후 2,1 삽입
[2,4,3] //1번 탐색 후 4,3 삽입
[2,4] //3번 탐색
[2] //4번 탐색
[6,5] //2번 탐색 후 6,5 삽입
[6] //5번 탐색
[] //6번 탐색 탐색 완료

이렇게 나중에 들어온 녀석을 먼저 탐색하는 식으로 생각할 수가 있죠? DFS는 스택! 이라고 생각해두시면 좋습니다.

저는 순환 호출을 통해 DFS 코드를 구현하고자 합니다.
이제부터는 코딩테스트에서도 많이 쓰이는 방식인데요.
우리는 방문 여부를 체크하기 위한 하나의 배열을 선언할 것입니다. 그 배열의 이름은 일반적으로 'visited'라고들 많이 사용해요.

해당 visited를 먼저 [0*(정점의개수)] 라고 초기화를 시켜둡니다. 그리고 해당 정점을 방문할 경우 0을 1로 변경시켜주는 것이죠. 즉 0=> 방문하지 않음, 1=> 방문함 이라고 표현하기로 약속을 하는 것입니다.

이제 dfs함수를 구현해보도록 하겠습니다.

DFS 주요 함수

void dfs_mat(GraphType* g,int v){
    int w;
    visited[v]=TRUE;
    printf("visit %d -> ",v);
    for (w=0;w<g->n;w++)
        if(g->adj_mat[v][w] && !visited[w])
            dfs_mat(g,w);
}

설명

하나하나 차근차근 이해를 해보도록 하겠습니다.
매개변수로는 그래프와, v값이 들어왔는데요. 이 dfs탐색을 하고자하는 정점의 인덱스를 의미합니다.

define을 통해서 TRUE는 1이라고 정의를 해놓았습니다. 따라서 visited[v] 값은 TRUE라고 변경을 해줍니다. 해당 인덱스를 탐색한다는 것 자체가 해당 인덱스의 정점을 방문했다는 의미이기 때문이죠.

이제 그 밑의 반복문이 중요합니다.
반복문은 그래프 전체의 정점의 개수만큼 반복됩니다. 반복을 하면서 v인덱스의 정점과 간선이 연결되어 있는 정점들을 찾아주죠. 그와 동시에 그렇게 연결되어 있는 정점의 index가 visited에서는 0값을 가지고 있다면?? 해당 정점은 방문처리가 되지 않은 정점이기 때문에 그 정점에 대해 순환 호출을 진행합니다.

이 부분만 이해를 하셔도, 전체 코드를 이해하는데에 아무런 문제가 없으실 것이라 생각합니다. 만약 이해가 되지 않으신다면 제가 이전에 진행했던 그래프 포스팅에서 인접행렬 그래프 파트를 보고 오시면 이해에 도움이 되실거라고 생각해요:)

정의한 dfs_mat 함수를 통해 그림으로 보여드린 트리 탐색을 직접 코드로 구현해보도록 하겠습니다. (인접 행렬 방식을 채택하였습니다.)

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,"overflow");
        return;
    }
    g->n++;
}


void insert_edge(GraphType* g,int start,int end){
    if(start>=g->n||end>=g->n){
        fprintf(stderr,"vertex index error");
        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;
    printf("visit %d -> ",v);
    for (w=0;w<g->n;w++)
        if(g->adj_mat[v][w] && !visited[w])
            dfs_mat(g,w);
}


int main(void){
    GraphType *g;
    g=(GraphType *)malloc(sizeof(GraphType));
    init(g);
    for(int i=0;i<7;i++)
        insert_vertex(g,i); //그래프 정점 생성
    insert_edge(g,0,1);  // 그래프 간선 생성
    insert_edge(g,0,2);
    insert_edge(g,1,3);
    insert_edge(g,1,4);
    insert_edge(g,2,5);
    insert_edge(g,2,6);
    printf("DFS\n");
    dfs_mat(g,0); //함수 수행
    printf("\n");
    free(g);
    return 0;
}

출력 결과
...
DFS
visit 0 -> visit 1 -> visit 3 -> visit 4 -> visit 2 -> visit 5 -> visit 6 ->

이론에서 설명했던 것과 같은 결과가 나오는 것을 확인하실 수 있습니다 :)

마무리

오늘 DFS에 대한 설명이 도움이 되셨나요??
DFS/BFS를 한 포스팅에 모두 담고 싶었는데, 내용이 난잡해질 수도 있다는 생각에 DFS에 대한 설명만 담기로 결정하였습니다. ㅎㅎ 다음 포스팅에서는 BFS로 찾아뵙도록 하겠습니다. 읽어주셔서 감사합니다:)