[알고리즘] Day3 - 1260번 DFS와 BFS

00 문제

01 DFS 알고리즘?

• Depth First Search, 깊이 우선 탐색이라는 뜻.
• 하나의 노드에서 시작하여 마지막 지점까지 계속 탐색하는 행동을 하는 알고리즘
• 즉, 시작점을 기준으로 가장 아래까지 이동하면서 탐색하는 방식 -> 스택을 이용하여 푸는 방식
• 스택에 값을 넣어주고, 그 값을 통해 확인하며 종료 조건은 스택이 비어있을 때이다.
• DFS의 장점은 깊은 곳에 있을수록 빨리 찾아낼 수 있다는 점
• 단점은 자칫하면 overflow가 날 수도 있고, 얻어진 해가 최단 거리라는 보장이 없다.

02 DFS 알고리즘 구현 방식

• 인접한 노드들을 표현하기 위해 NxN 크기의 adj_mat 배열과 방문한 노드를 표현하기 위해 Nx1 크기의 visited 배열을 사용한다. 
• add_matrix 함수에서 연결된 노드를 입력받고, 해당 값을 1로 설정한다.
• Stack을 이용해 DFS를 구현하는 방식은 다음과 같다.

- 현재 기준점이 되는 정점을 row 변수에 저장한다. 

- 반복을 위해 i 변수를 이용한다. push 또는 pop 할 때 초기화된다.

- row 와 i 노드가 연결되어 있고 i 노드를 방문하지 않았을 경우 push

- i 변수가 N과 같아지면 지나갈 노드가 없다는 뜻이므로 pop

- 모든 노드를 pop해서 stack이 비어있으면 종료한다.

bool *adj_mat, *visited;

N += 1;        // 정점의 번호는 1부터 시작한다.

adj_mat = (bool *)calloc(N*N, sizeof(bool));

visited = (bool *)calloc(N, sizeof(bool));

void add_matrix(int N, int M)

{

        int i;

        int v1, v2;

        // input

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

        {

               scanf_s("%d %d", &v1, &v2);

               adj_mat[v1*N + v2] = 1;

               adj_mat[v2*N + v1] = 1;

        }

}

void depth_first_search(int N, int V)

{

        int i = 0;

        int row = V;

        printf("%d ", push(V));

        

        while (is_empty())

        {

               visited[row] = 1;

               if (adj_mat[row*N + i] == 1 && !visited[i])

               {

                       printf("%d ", push(i));

                       row = i;

                       i = 0;

               }

               if (i == N)

               {

                       pop(); 

                       row = top();

                       i = 0;

               }

               i++;

        }

}

03 BFS 알고리즘?

• Breadth First Search, 너비 우선 탐색이라는 뜻.
• 시작점을 기준으로 DFS와 마찬가지로 가장 아래까지 이동하면서 탐색 -> 큐를 이용하는 방식
• BFS는 깊이 탐색과 다르게 인접한 노드를 차례대로 방문한다.
• 큐에 값을 넣어주고, 그 값을 통해 확인하며 종료 조건은 큐가 비어있을 때이다.

04 BFS 알고리즘 구현 방식

• 인접한 노드들을 표현하기 위해 NxN 크기의 adj_mat 배열과 방문한 노드를 표현하기 위해 Nx1 크기의 visited 배열을 사용한다. 
• add_matrix 함수에서 연결된 노드를 입력받고, 해당 값을 1로 설정한다.
• Queue를 이용해 BFS를 구현하는 방식은 다음과 같다.
  1) queue의 가장 앞에 있는 노드를 get
  2) 현재 노드에 인접한 모드 노드들 중 아직 방문하지 않은 노드들을 queue에 put
  3) queue가 비어있지 않으면 1)부터 다시 실행

void breath_first_search(int N, int V)

{

        int i = 0;

        int row = V - 1;

        printf("%d ", put(V));

        while (is_empty())

        {

               visited[row] = 1;

               

               get();  

                       

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

               {

                       if (adj_mat[row*N + i] == 1 && !visited[i])

                       {

                              printf("%d ", put(i));

                              visited[i] = 1;

                       }

               }

               row = top();

        }

}

05 전체 소스 코드

#include "stdafx.h"

#include "data_structure.h"

void add_matrix(int N, int M);

void print_matrix(bool* matrix, int N);

void depth_first_search(int N, int V);

void breath_first_search(int N, int V);

bool *adj_mat, *visited;

int main()

{

        int i, N, M, V;

        scanf_s("%d %d %d", &N, &M, &V);

        N += 1;        // 정점의 번호는 1부터 시작한다.

        adj_mat = (bool *)calloc(N*N, sizeof(bool));

        visited = (bool *)calloc(N, sizeof(bool));

        init_node();

        add_matrix(N, M);

        //print_matrix(adj_mat, N);

        printf("- - - - - - - \n");

        depth_first_search(N, V);

        

        clear_node();

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

               visited[i] = 0;

        printf("\n");

        breath_first_search(N, V);

        printf("\n");

        // finish

        free(adj_mat);

        free(visited);

    return 0;

}

void add_matrix(int N, int M)

{

        int i;

        int v1, v2;

        // input

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

        {

               scanf_s("%d %d", &v1, &v2);

               adj_mat[v1*N + v2] = 1;

               adj_mat[v2*N + v1] = 1;

        }

}

void print_matrix(bool* matrix, int N)

{

        int i, j;

        // print

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

        {

               printf("row %d = ", i);

               for (j = 0; j < N; ++j)

               {

                       printf("%d ", matrix[i*N + j]);

               }

               printf("\n");

        }

}

void depth_first_search(int N, int V)

{

        int i = 0;

        int row = V;

        printf("%d ", push(V));

        

        while (is_empty())

        {

               visited[row] = 1;

               if (adj_mat[row*N + i] == 1 && !visited[i])

               {

                       printf("%d ", push(i)); 

                       row = i;

                       i = 0;

               }

               if (i == N)

               {

                       pop();  

                       row = top();

                       i = 0;

               }

               i++;

        }

}

void breath_first_search(int N, int V)

{

        int i = 0;

        int row = V;

        printf("%d ", put(V)); 

        while (is_empty())

        {

               visited[row] = 1;

               if (top() == row)

                       get();  

                       

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

               {

                       if (adj_mat[row*N + i] == 1 && !visited[i])

                       {

                              printf("%d ", put(i)); 

                              visited[i] = 1;

                       }

               }

               row = top();

        }

}

06 data_structer header

#include <stdlib.h>

typedef struct _dnode {

        int key;

        struct _dnode *prev;

        struct _dnode *next;

}dnode;

dnode *head, *tail;

void init_node()

{

        head = (dnode *)calloc(1, sizeof(dnode));

        tail = (dnode *)calloc(1, sizeof(dnode));

        head->prev = head;

        head->next = tail;

        tail->prev = head;

        tail->next = tail;

}

/* * * * * * * * * * * * *

**      Stack push and pop * *

** * * * * * * * * * * * */

int push(int k)

{

        dnode *t;

        if ((t = (dnode *)malloc(sizeof(dnode))) == NULL)

        {

               printf("Out of memory !\n");

               return -1;

        }

        t->key = k;

        head->next->prev = t;

        t->next = head->next;

        t->prev = head;

        head->next = t;

        return k;

}

int pop()

{

        dnode *t;

        int k;

        if (head->next == tail)

        {

               printf("Stack underflow !\n");

               return -1;

        }

        t = head->next;

        k = t->key;

        head->next = t->next;

        t->next->prev = head;

        free(t);

        return k;

}

/* * * * * * * * * * * * *

**      Queue put and get  * *

** * * * * * * * * * * * */

int put(int k)

{

        dnode *t;

        if ((t = (dnode*)malloc(sizeof(dnode))) == NULL)

        {

               printf("Out of memory !! \n");

               return -1;

        }

        t->key = k;

        tail->prev->next = t;

        t->prev = tail->prev;

        tail->prev = t;

        t->next = tail;

        return k;

}

int get()

{

        dnode *t;

        int k;

        t = head->next;

        if (t == tail)

        {

               printf("Queue undeflow !! \n");

               return -1;

        }

        k = t->key;

        head->next = t->next;

        t->next->prev = head;

        free(t);

        return k;

}

void clear_node()

{

        dnode *t, *s;

        t = head->next;

        while (t != tail)

        {

               s = t;

               t = t->next;

               free(s);

        }

        head->next = tail;

        tail->prev = head;

}

void print_node()

{

        dnode *t;

        t = head->next;

        while (t != tail)

        {

               printf("%-6d", t->key);

               t = t->next;

        }

}

int is_empty()

{

        if (head->next == tail)

        {

               //printf("Linked list is empty !\n");

               return 0;

        }

        return 1;

}

int top()

{

        dnode *t;

        t = head->next;

        if (t == tail)

               return -1;

        return t->key;

}

int bottom()

{

        dnode *t;

        t = tail->prev;

        if (t == head)

               return -1;

        return t->key;

}

int is_in_stack(int k)

{

        dnode *t;

        t = head->next;

        while (t != tail)

        {

               if (t->key == k)

                       return 1;

               t = t->next;

        }

        return 0;

}

99 참고자료

• [백준 알고리즘 1260번: DFS와 BFS] https://www.acmicpc.net/problem/1260
• [DFS 알고리즘] http://www.crocus.co.kr/520
• [BFS 알고리즘] http://www.crocus.co.kr/521
• [BFS 알고리즘] http://sarah950716.tistory.com/13