[백준] 1717번 집합의 표현

 

 

문제

 

 

소스코드

#include<iostream>
#include<vector>
#include<string>
#include<string_view>
using vector_t = std::vector<int>;
 
constexpr int MAX_N      = 1000001;
constexpr int MAX_M      = 100001;
constexpr int COMBINE    = 0;
constexpr int CHECK      = 1;
 
void Make_Set(vector_t& nodes,int size) {
    for (int i = 1; i <= size; ++i) {
        nodes[i] = i;
    }
}
 
int Find(vector_t& nodes, int v) {
    if (nodes[v] == v)
        return v;
    else
        return nodes[v] = Find(nodes, nodes[v]);
}
 
void Union(vector_t& nodes, int lhs, int rhs) {
    int lhs_parent = Find(nodes, lhs);
    int rhs_parent = Find(nodes, rhs);
 
 
    if (lhs_parent < rhs_parent)
        nodes[rhs_parent] = lhs_parent;
    else
        nodes[lhs_parent] = rhs_parent;
 
}
 
std::string_view Check_Node(vector_t& nodes, int lhs, int rhs) {
    int lhs_parent = Find(nodes, lhs);
    int rhs_parent = Find(nodes, rhs);
 
    if (lhs_parent == rhs_parent)
        return "YES";
    else
        return "NO";
}
 
 
 
int main() {
    int N, M;
    vector_t nodes;
    std::vector<std::string> print_v;
    std::cin >> N >> M;
 
    nodes.assign(N+1, 0);
    Make_Set(nodes,N);
 
    for (int i = 0; i < M; ++i) {
        int kind, lhs, rhs;
        std::cin >> kind >> lhs >> rhs;
 
        if (kind == COMBINE) {
            Union(nodes, lhs, rhs);
        }
        else if (kind == CHECK) {
            print_v.emplace_back(Check_Node(nodes, lhs, rhs));
        }
    }
 
    for (const auto& i : print_v) {
        std::cout << i << "\n";
    }
 
}

 

후기

이 문제를 해결하기 위한 키워드는 2가지이다.

 

1. Union-Find

    Unino-FInd란 Disjoint Set(중복되지 않은 부분 집합들)을 표현하고자 할 때 사용하는 알고리즘이다.

    1-1. Make_set() 메서드를 통해서 각 원소는 자기 자신을 부모로 가지게 한다.

 

    1-2. Union() 메서드에서는 두 원소를 받은 뒤 각 원소에 부모 노드를 받고 두 원소를 비교 후 더 작은 원소에 큰 원소를

        붙인다.

    

    1-3. Find() 메서드에서는 노드의 집합 nodes에 원소가 자기 자신인지 확인 후 return 한다.

        이때 Union-find에서의 최악의 상황 중 하나인 연결 리스트와 동일한 형태가 된다면 시간 복잡도가 O(N)

        이 되기 때문에 find 연산을 하면서 찾은 부모 노드들을 마지막 부모 노드(root)에 붙인다.

    

2.  같은 집합에 있는가?

     두 원소가 같은 집합에 있는지 확인하는 방법은 Check_Node() 메서드에 구현하였으며 두 원소의 부모 노드가

     동일하다면 같은 집합에 있는 것이므로 출력용 vector에 넣고 출력하였다.

 

* 해당 문제는 C++17 표준의 std::string_view를 사용했으므로 C++17 이상의 컴파일러를 지원하는 환경에서만 작동합니다.

 

출처 및 레퍼런스

문제 링크:https://www.acmicpc.net/problem/1717

 

관련 글

합집합 찾기(Union-Find)

[백준] 1197번 최소 스패닝 트리

 

* 2020.05.13

폰트 색상 및 Colir Scripter로 변경