M'S Blog

M'S Blog

WWDC20 student challenge Winner!

Graph - 연결 요소

1 분 소요

연결 요소(Connected Component)

위의 이미지는 그래프가 1개 일까 2개 일까??

정답은 1개와 2개 모두 맞다.

1개라면 단지 연결하는 간선이 없는 그래프이고

2개라면 우연히 정점이 겹치지 않는 각각의 그래프이다.

그래프가 1개라면, __나누어진 각각의 그래프를 연결 요소__라고 한다.

즉, 위의 그림으로 보자면 노란색 연결 요소 하나 파란색 연결 요소하나 이렇게 총 2개의 연결요소로 이루어진 그래프가 되는 것이다.

연결 요소의 조건

  • 연결 요소에 속한 모든 정점들은 끊어지면 안되고, 서로 연결 되어 있어야 한다.
  • 다른 연결 요소에 속한 정점과 연결되는 간선이 있어선 안된다.

연결 요소 문제

DFS나 BFS 탐색을 이용하여 구할 수 있다.

  • 문제

    백준 11724번 - 연결요소의 개수

  • 풀이

    1. dfs(재귀함수) 이용 - 연결리스트

      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
      #include <cstdio>
      #include <algorithm>
      #include <vector>
       
      using namespace std;
       
      int component = 0;
       
      vector<int> list[1001];
      bool check[1001];
       
      void dfs(int v) {
          check[v] = true;
          for (int i = 0; i < list[v].size(); i++) {
              int next = list[v][i];
              if (!check[next]) {
                  dfs(next);
              }
          }
      }
       
      int main() {
          int n, m;
       
          scanf("%d %d", &n, &m);
       
          for (int i = 0; i < m; i++) {
              int u, v;
              scanf("%d %d", &u, &v);
              list[u].push_back(v);
              list[v].push_back(u);
          }
       
          for (int i = 1; i <= n; i++) {
              sort(list[i].begin(), list[i].end());
          }
       
          for (int i = 1; i <= n; i++) {
              if (!check[i]) { //false일 때(방문 하지 않았을 때)
                  component++;
                  dfs(i);
              }
          }
       
          printf("%d", component);
          
      }
      		cs
      • 굳이 sort 할 필요 없는데(어느 정점부터 방문 할 것인지랑은 상관 없어서) 그냥 sort 쓰고 싶어서 추가해봤어요….ㅎ * 38~43의 for문 : 정점 1번부터 n번째 정점까지 반복문을 사용해서 해당 정점을 방문했는지 아닌지 파악한다. 이때 방문하지 않았다면, dfs 탐색을 시작한다. dfs는 재귀함수로 구현되어 있으므로, 탐색이 끝나면 다시 반복문으로 돌아온다. 그리고 반복문을 통해 방문하지 않은 정점이 있는지 파악한다. 방문하지 않은 정점은 이전에 탐색되지 않은 새로운 연결 요소의 시작이므로 component 변수에 +1을 해준다.

  1. bfs 이용 - 연결리스트

    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
    #include <cstdio>
    #include <algorithm>
    #include <vector>
    #include <queue>
     
    using namespace std;
     
    int component = 0;
     
    vector<int> list[1001];
    bool check[1001];
     
    queue<int> q;
     
    void bfs(int v) {
        check[v] = true;
        q.push(v);
        while (!q.empty()) {
            int current = q.front();
            for (int i = 0; i < list[current].size(); i++) {
                int next = list[current][i];
                if (!check[next]) {
                    check[next] = true;
                    q.push(next);
                }
            }
            q.pop();
        }
    }
     
    int main() {
        int n, m;
     
        scanf("%d %d", &n, &m);
     
        for (int i = 0; i < m; i++) {
            int u, v;
            scanf("%d %d", &u, &v);
            list[u].push_back(v);
            list[v].push_back(u);
        }
     
        for (int i = 1; i <= n; i++) {
            sort(list[i].begin(), list[i].end());
        }
     
        for (int i = 1; i <= n; i++) {
            if (!check[i]) { //false일 때(방문 하지 않았을 때)
                component++;
                bfs(i);
            }
        }
     
        printf("%d", component);
    }
    		cs
    • 47~50의 for문 : 정점 1번부터 n번째 정점까지 반복문을 사용해서 해당 정점을 방문했는지 아닌지 파악한다. 이때 방문하지 않았다면, bfs 탐색을 시작한다. bfs는 queue가 빌 때까지 진행되므로, 탐색이 끝나면 다시 반복문으로 돌아온다. 그리고 반복문을 통해 방문하지 않은 정점이 있는지 파악한다. 방문하지 않은 정점은 이전에 탐색되지 않은 새로운 연결 요소의 시작이므로 component 변수에 +1을 해준다.





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

</html>

댓글남기기

참고