M'S Blog

M'S Blog

WWDC20 student challenge Winner!

백준 2606 - 바이러스

최대 1 분 소요

문제

백준 2606 - 바이러스 풀러가기

문제 풀이

이 문제를 보고 처음 떠오른 풀이는 연결 요소 를 구하듯이 푸는 것이다. (연결 요소에 대한 설명이 필요하다면)

그래서 bfs를 이용하여 손쉽게 풀 수 있었다.

두번째로 풀 수 있는 방법은 Union Find를 이용하는 것이다.

root가 같은지 확인하면 되기 때문이다.

문제 코드(C++)

  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
    #include <cstdio>
    #include <vector>
    #include <queue>
     
    using namespace std;
     
    int main() {
        int n, p;
     
        scanf("%d", &n);
        scanf("%d", &p);
     
        vector<vector<int>> a(n+1);
        vector<bool> visit(n+1);
     
        for (int i = 0; i < p; i++) {
            int x, y;
            scanf("%d %d", &x, &y);
     
            a[x].push_back(y);
            a[y].push_back(x);
        }
     
        queue<int> q;
        q.push(1);
        visit[1] = true;
        int cnt = 0;
     
        while (!q.empty()) {
            int cur = q.front();
            q.pop();
            for (int i = 0; i < a[cur].size(); i++) {
                int next = a[cur][i];
                if (visit[next] == false) {
                    cnt++;
                    visit[next] = true;
                    q.push(next);
                }
            }
        }
     
        printf("%d", cnt);
     
        return 0;
    }
    		cs
    • 16~22번째 줄 : 인접 리스트를 통해 그래프를 표현했다. (인접리스트에 대한 설명이 필요하다면)
    • 24~40번째 줄 : 정점 1부터 시작하여, 1에 연결된 정점들을 방문하고, 방문 시에 count를 증가시켜준다.

  2. 전체 코드(유니온 파인드 이용)

    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
    #include <cstdio>
    #include <vector>
     
    using namespace std;
     
    vector<int> parent;
     
    int Find(int x) {
        if (x == parent[x]) {
            return x;
        }
        else {
            parent[x] = Find(parent[x]);
            return parent[x];
        }
    }
     
    void Union(int x, int y) {
        x = Find(x);
        y = Find(y);
     
        if (x != y) {
            parent[y] = x;
        }
    }
     
    int main() {
        int n, p;
     
        scanf("%d", &n);
        scanf("%d", &p);
     
        parent.resize(n + 1);
     
        for (int i= 1; i <= n; i++) {
            parent[i] = i;
        }
     
        for (int i = 0; i < p; i++) {
            int x, y;
            scanf("%d %d", &x, &y);
            Union(x, y);
        }
        int ans = 0;
        int root = Find(1);
        for (int i = 2; i <= n; i++) {
            if (root == Find(i)) {
                ans++;
            }
        }
        printf("%d", ans);
     
        return 0;
    }
    		cs
    • 35~37번째 줄 : 처음에는 현재 요소를 parent로 초기화한다.
    • 39~40번째 줄 : 연결 정보를 입력 받고, union을 통해 x와 y가 포함되어 있는 집합을 합친다.
    • 45번째 줄 : 1의 root를 찾는다.
    • 46~50번째 줄 : 위에서 찾은 root와 같은 root를 가지는 집합의 원소가 있다면 count를 증가시킨다.





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

댓글남기기

참고