M'S Blog

M'S Blog

WWDC20 student challenge Winner!

Graph의 탐색 - DFS, BFS(작성중)

2 분 소요

그래프 탐색의 목적

그래프의 모든 정점 을 한번씩 방문하기 위해!

그래프 탐색 알고리즘

  1. 깊이 우선 탐색(Depth First Search, DFS)
    • 한 길을 깊이 파고 들어 더 이상 갈 수 없으면 이전 정점으로 돌아감.
    • stack 이용
  2. 너비 우선 탐색(Breadth First Search, BFS)
    • 현재 정점이 갈 수 있는 모든 정점을 방문하는 것(동시에)
    • queue 이용

DFS

설명

  • stack 과 실제로 한번씩 방문 한 것이 맞는지 확인을 위한 배열 을 이용한다.

    • 갈 수 있는 만큼 최대한 많이 가고, 더 이상 갈 수 없다면 stack을 통해 이전 정점으로 돌아간다.

  • 방문의 우선 순위는 정하기 나름이다. 코드 짜는 사람 맴이지롱

  1. 현재 정점은 1이고 stack에는 1이 있다. 다음으로 갈 수 있는 정점은 2,3,4가 있는데 여기서는 가장 작은 정점을 우선적으로 가는 걸로 하겠다.

  1. 정점 2를 방문하였고, stack에는 2를 push한다.

  1. 2에서 방문 가능한 정점, 3을 방문했고 stack에는 3이 push 된다.

  1. 3에서 방문 가능한 정점 5, 6 중 작은 숫자인 정점 5를 방문하고 5를 push한다.

  1. 5에서 방문 가능한 정점 6을 가고, stack에 6을 push 한다.

  1. 정점 6에서 더 이상 갈 수 있는 곳이 없다.
    1. stack을 이용하여 이전 정점으로 되돌아간다.
    2. 아래의 경우 pop을 하면 head값이 5가 되므로, 정점 5로 돌아간다.

  1. 정점 5에서 더 이상 갈 수 있는 곳이 없으므로 stack에서 5를 pop하여 정점 3으로 돌아간다.

  1. 정점 3에서 더 이상 갈 수 있는 곳이 없으므로 stack에서 3를 pop하여 정점 2로 돌아간다.

  1. 정점 2에서 더 이상 갈 수 있는 곳이 없으므로 stack에서 2를 pop하여 정점 1로 돌아간다.

  1. 정점 1에서 4로 갈 수 있으므로 정점 4를 방문하고 stack에 4를 push한다.

  1. 정점 4에서 더 이상 갈 수 있는 곳이 없으므로 pop하여 정점 1로 돌아간다.

  1. 정점 1에서 더 이상 갈 수 있는 곳이 없어 pop을 하면 stack이 비게 된다. stack이 비게 되면 탐색을 종료한다.

BFS

설명

  • queue 와 실제로 한번씩 방문 한 것이 맞는지 확인을 위한 배열 을 이용한다.

    • DFS에서는 실제로 정점을 방문 했을 경우에 해당 정점을 stack에 push하고 배열의 값을 1로(방문의 표시) 바꿔주었다.
    • 하지만 BFS에서는 지금 위치에서 갈 수 있는 모든 정점을 큐에 넣고, 큐에 넣었을 때 배열의 값을 1로 (방문했다고 표시) 바꿔주어야 한다.(즉, 실제로 아직 방문하지 않았지만 큐에 넣고, 배열에도 체크 해줘야 한다는 말)
  1. 현재 정점은 1이고, 큐에는 1을 넣어준다.

  1. 1에서 갈 수 있는 모든 정점(2,3,4)를 큐에 넣고 배열의 값도 1로 바꿔줍니다.

  1. 그리고 1을 큐에서 제거하고 다음 front의 값인 2를 현재 정점으로 합니다.

  1. 2에서는 갈 수 있는 곳이 없으므로, 큐에서 2를 제거하고 현재 정점은 3이 됩니다.

  1. 3에서는 정점 5와 6에 갈 수 있으므로, 5와 6을 큐에 넣고 배열에 1로 체크 해 줍니다.

  1. 3을 큐에서 제거하고 현재 정점은 4가 됩니다.

  1. 4에서는 더 이상 갈 수 있는 곳이 없으므로, 큐에서 빠져나오고 현재 정점은 5가 됩니다.

  1. 5에서는 더 이상 갈 수 있는 곳이 없으므로, 큐에서 빠져나오고 현재 정점은 6이 됩니다.

  1. 6에서는 더 이상 갈 수 있는 곳이 없으므로, 큐에서 빠져나오고 큐는 비어있게 됩니다. 큐에 아무것도 없으면 탐색 완료!

문제 풀어 보기(구현)

백준 DFS와 BFS 문제

  1. 인접 행렬을 이용한 풀이

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    #include <queue>
    #include <cstdio>
    #include <vector>
    #include <cstring>
     
    using namespace std;
     
    bool check[1001];
    int matrix[1001][1001];
    int n;
    queue<int> q;
     
    void dfs(int v) {
        printf("%d ", v);
        check[v] = true;
        for (int i = 1; i <= n; i++) {
            if (matrix[v][i] == 1 && check[i] == false) {
                dfs(i);
            }
        }
    }
     
    void bfs(int v) {
        memset(check, false, sizeof(check));
        q.push(v);
        check[v] = true;
        while (!q.empty()) {
            int current = q.front();
            printf("%d ", current);
            for (int i = 1; i <= n; i++) {
                if (matrix[current][i] == 1 && check[i] == false) {
                    check[i] = true;
                    q.push(i);
                }
            }
            q.pop();
        }
    }
     
    int main() {
        int m, v;
        scanf("%d %d %d", &n, &m, &v);
     
        for (int i = 0; i < m; i++) {
            int r, c;
            scanf("%d %d", &r, &c);
            matrix[r][c] = 1;
            matrix[c][r] = 1;
        }
     
        dfs(v);
        printf("\n");
        bfs(v);
     
        return 0;
    }
    		cs
    • dfs의 경우에는 재귀 함수를 이용하였다.
    • 정점의 개수가 1부터 1000까지의 값을 가질 수 있으므로 배열을 1001까지로 만들어서 배열 인덱스를 1부터 1000까지 다 접근 할 수 있도록 만들었다.

  2. 인접 리스트를 이용한 풀이

    1. 재귀 함수 이용

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      55
      56
      57
      58
      59
      60
      61
      #include <cstdio>
      #include <queue>
      #include <algorithm>
      #include <cstring>
       
      using namespace std;
       
      bool check[1001];
      vector<int> list[1001];
      queue<int> q;
       
      void dfs(int v) {
          printf("%d ", v);
          check[v] = true;
          for (int i = 0; i < list[v].size(); i++) {
              int next = list[v][i];
              if (check[next] == false) {
                  dfs(next);
              }
          }
      }
       
      void bfs(int v) {
          memset(check, false, sizeof(check));
          q.push(v);
          check[v] = true;
          while (!q.empty()) {
              int current = q.front();
              printf("%d ", current);
              for (int i = 0; i < list[current].size(); i++) {
                  int next = list[current][i];
                  if (check[next] == false) {
                      q.push(next);
                      check[next] = true;
                  }
              }
              q.pop();
          }
      }
       
      int main() {
          int n, m, v;
          scanf("%d %d %d", &n, &m, &v);
       
          for (int i = 0; i < m; i++) {
              int r, c;
              scanf("%d %d", &r, &c);
              list[r].push_back(c);
              list[c].push_back(r);
          }
       
          for (int i = 1; i <= n; i++) {
              sort(list[i].begin(), list[i].end());
          }
       
          dfs(v);
          printf("\n");
          bfs(v);
       
          return 0;
      }
      		cs
      • sort가 들어간 이유는, 문제의 조건에 ‘방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고’라는 말이 있기 때문이다.

    2. stack 이용

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      55
      56
      57
      58
      59
      60
      61
      62
      63
      64
      65
      66
      67
      68
      69
      70
      71
      72
      73
      74
      #include <cstdio>
      #include <queue>
      #include <stack>
      #include <algorithm>
      #include <cstring>
       
      using namespace std;
       
      bool check[1001];
      vector<int> list[1001];
      queue<int> q;
      stack<int> s;
       
      void dfs(int v) {
          check[v] = true;
          s.push(v);
          printf("%d ", v);
          while (!s.empty()) {
              int current = s.top();
              int i = 0;
              for (; i < list[current].size(); i++) {
                  int next = list[current][i];
                  if (check[next] == false) {
                      printf("%d ", next);
                      check[next] = true;
                      s.push(next);
                      break;
                  }
              }
              if (i == list[current].size()) {
                  s.pop();
              }
          }
      }
       
      void bfs(int v) {
          memset(check, false, sizeof(check));
          q.push(v);
          check[v] = true;
          while (!q.empty()) {
              int current = q.front();
              printf("%d ", current);
              for (int i = 0; i < list[current].size(); i++) {
                  int next = list[current][i];
                  if (check[next] == false) {
                      q.push(next);
                      check[next] = true;
                  }
              }
              q.pop();
          }
      }
       
      int main() {
          int n, m, v;
          scanf("%d %d %d", &n, &m, &v);
       
          for (int i = 0; i < m; i++) {
              int r, c;
              scanf("%d %d", &r, &c);
              list[r].push_back(c);
              list[c].push_back(r);
          }
       
          for (int i = 1; i < n; i++) {
              sort(list[i].begin(), list[i].end());
          }
       
          dfs(v);
          printf("\n");
          bfs(v);
       
          return 0;
      }
      		cs
      • 30 ~ 32 의 if 문 : i의 값이 정점 n에 연결된 정점들의 개수와 같다면 해당 정점에서 더 이상 갈 수 있는 곳이 없음을 의미하므로 pop을 해준다.

  3. 간선의 정보를 이용

응용

  1. 연결 요소 찾기

  2. 이분 그래프






    아직 배움의 과정에 있는 학생이니 내용에 부족한 점이 보이면 지적은 하되, 비난은 하지 말아주세요!!

</html>

댓글남기기

참고