깊이 우선 순회 DFS - 스택 이용

#define MAX 50



class Node {

    int vertex;  //정점(노드)

    Node *link; //정점(노드)와 연결된 다른 노드

} *graph[MAX], *w;



int visited[MAX];



main()

{

    int i, s;

    for(i = 0; i < MAX; i++)

        visited[i] = FALSE;

    s = 0;  // s = 시작 노드;

    DFS(s);

}

간단하게 스택구조를 설명하기로 한다. 스택은 입구가 1개. 들어가는 부분으로 나온다고 생각하면 된다.

즉, 그림에서처럼 윗부분은 뚫렸기 때문에 데이터가 들어가거나 나올 수 있지만, 하단은 막혀있기 때문에 하단으로는 데이터가 드나들 수 없다.

어떻게 본다면 스택은 마치 접시를 쌓아놓는 구조와 같다.

다음과 같이 접시를 하나하나 차곡차곡 쌓아 올린 경우, 보통은 접시를 맨 윗쪽에서 빼기 마련이다.

안그러면 접시 탑이 무너져서 그릇이 깨질 수 있다.

혹은 프링글스 통처럼 생겼다고 가정할수도 있다. 일반적으로 하나하나 꺼내려면 입구에 있는 맨 윗부분의 감자칩부터 꺼내기 마련이다.

다음의 스택구조를 살펴보자.

1번 데이터가 들어온 뒤 2번 데이터가 들어왔고 그다음은 3번 데이터가 차례차례 순서대로 들어온 상황이다.

이 상황에서, 데이터를 가져가려면 3번 데이터부터 빼와야 한다.

1번은 가장 바닥쪽에 위치해있기 때문에, 1번 데이터를 가져가려면 3,2,1 순서로 꺼내와야 한다.

이렇게 간단하게 스택 구조를 살펴봤다.

이제는 스택을 이용한 DFS를 이해해보도록 하자.

 

void DFS(int v)

{

    push(v);

    while(!stack_empty())    //스택이 비었는지 채워져 있는지 확인하는 함수 stack_empty()

    {

        v = pop();

        visited[v] = TRUE;

        print_node(v);

        for(w = graph[v]; w; w = w->link)

        if(!visited[w->vertex])

        push(w->vertex);

    }

}

 

main()에서 visited[v]의 배열의 원소들을 FALSE로 초기화 해주었다.

깊이 우선 순위 DFS의 스택을 활용한 방법을 배우기 위한 예제는 다음과 같다.

DFS 함수의 구조를 간단히 살펴보자.

단, 이 알고리즘은 배열이 0으로 시자하는 것이 아니라, 1부터 시작한다는 것을 가정한다.

 

void DFS(int s)               //함수의 매개변수는 s로, main()에서 시작 노드로 전해준 변수이다.

{

    push(s);

    while(!stack_empty())  //스택이 비었는지 채워져 있는지 확인하는 함수 stack_empty()

                                  //스택이 비어있다면 TRUE를 반환, 하나 이상의 노드가 있다면 FALSE를 반환한다.

                                  //따라서 스택이 비어있지 않다면 while()을 반복 실행하게 된다.

    {

        v = pop();

        visited[v] = TRUE;

        print_node(v);

        for(w = graph[v]; w; w = w->link)

        if(!visited[w->vertex])

        push(w->vertex);

    }

}

 

 

이제, 맨 처음으로 반복문에 진입한 경우,

void DFS(int s)

{

    push(s);                             //시작노드인 V1을 스택에 push() 해준다. [그림1]

    while(!stack_empty())            //스택에 시작노드인 V1이 있기 때문에 while()을 실행한다.

                                          //stack_empty()는 FALSE를 반환하지만 !FALSE이기 때문에 TRUE여서 while실행

    {

        v = pop();                    //시작노드인 V1을 pop()해서 v에 대입. 여기서 pop한 것은 노드의 vertex인 1. [그림2]

        visited[v] = TRUE;          //그리고 V1을 방문했다는 것을 표시해주기 위해서

                                        //visited[]배열의 1번 인덱스에 해당하는 값을 TURE로 전환 => visited[1]=TRUE;

        print_node(v);              //1을 보여준다.

        for(w = graph[v]; w; w = w->link)    //graph[v]의 원소인 V1을 w에 대입,

        if(!visited[w->vertex])                    // w->vertex : w노드의 정점(노드), 여기서는 1을 의미.

                                                       //위의 visited[v] = TRUE;를 해주었으므로, visited[1]=TRUE이기 때문에

                                                       //!TRUE = FALSE이므로 

        push(w->vertex);                         //push하지 않는다.

    }

}

 

 그리고 다시 for문으로 돌아간다.

        for(w = graph[v]; w; w = w->link)    //w에 연결된 링크를 w에 대입. 여기서는 1과 연결된 노드인 2를 대입.

        if(!visited[w->vertex])                    // w->vertex : w노드의 정점(노드), 여기서는 2을 의미.

                                                       //visited[2]=FALSE이기 때문에

                                                       //!FALSE=TRUE이므로 

        push(w->vertex);                         //w의 vertex인 2를 push한다. [그림3]

 

그리고 다시 for문으로 돌아간다.

        for(w = graph[v]; w; w = w->link)    //w에 연결된 링크를 w에 대입. 여기서는 1과 연결된 노드인 2를 대입.

        if(!visited[w->vertex])                    // w->vertex : w노드의 정점(노드), 여기서는 2을 의미.

                                                       //visited[2]=FALSE이기 때문에

                                                       //!FALSE=TRUE이므로 

        push(w->vertex);                         //w의 vertex인 2를 push한다. [그림3]

코드를 이해한다면 쉽게 정리가 가능하지만, 코드 없이 알고리즘으로만 이해해야 하거나 코드가 제시되지 않은 상황에서 문제를 풀어야 할 때, 위에서 설명한 내용을 보고 스스로 정리 해야 하는 내용은 다음과 같다. 

 

1) push는 언제까지 push 해야하는 걸까?

2) 만약 push할 노드가 없다면 어떻게 해야할까?

3) pop은 언제까지 pop해야하는 걸까?

 

이 물음들에 답할 준비가 되었다면 이것으로 DFS는 마무리 한다.