[백준] 17352번 여러분의 다리가 되어 드리겠습니다!

 

문제

소스코드

#include<iostream>
#include<vector>
 
int Find(const int i, std::vector<int>& g) {
    if (g[i] == i)
        return i;
    else
        return g[i] = Find(g[i], g);
}
 
void Union(const int lhs, const int rhs, std::vector<int>& g, std::vector<int>& r) {
    int lhs_parent = Find(lhs, g);
    int rhs_parent = Find(rhs, g);
 
    //같은 집합이면 stop
    if (lhs_parent == rhs_parent)return;
 
    //랭크가 더 높은걸 작은쪽으로 합친다.
    if (r[lhs_parent] > r[rhs_parent]) {
        g[rhs_parent] = lhs_parent;
    }
    else {
        g[lhs_parent] = rhs_parent;
        if (r[lhs_parent] == r[rhs_parent]) {
            r[lhs_parent]++;
        }
    }
}
 
bool SearchSameParent(const int lhs, const int rhs, std::vector<int>& g) {
    int lhs_parent = Find(lhs, g);
    int rhs_parent = Find(rhs, g);
 
    if (lhs_parent == rhs_parent)return true;
 
    return false;
}
 
int main() {
 
    //C++ 입출력 속도
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
 
    int n{};
    std::cin >> n;
    std::vector<int> g(n + 1, 0);
    std::vector<int> r(n + 1, 0);
 
    //make graph
    for (int i = 1; i <= n; ++i)
        g[i] = i;
 
    //N-2개 까지 받는다.
    for (int i = 1; i <= n - 2; ++i) {
        int lhs, rhs;
        std::cin >> lhs >> rhs;
        Union(lhs, rhs, g, r);
    }
 
    for (int i = 1; i <= n - 1; ++i) {
        if (SearchSameParent(i, i + 1, g) == false) {
            std::cout << i << " " << i + 1 << "\n";
            break;
        }
    }
}

후기

이 문제를 해결하기 위한 키워드는 Union-Find이다.

 

Union-Find 상호 배타적 집합(Union-Find Disjoint Set, UFDS)은 상호 배타적인 집합들의 모임을 모델링하는 자료 구조이며 원소가 어느 집합에 속해있는지 판별하는 알고리즘이다.

 

이 문제 또한 섬이라는 집합을 가지고 두 섬이 연결되어 있는지 여부에 따라 다리를 놓는 문제이기 때문에 Union-Find를 사용하기 좋은 문제이다. 

 

여담으로 시간 초과가 계속 발생해서 확인해보았는데 Union()에서 rank vector를 & 인자를 때고 넘겨줘서 시간 초과가 발생했다. 복사 생성자가 얼마나 많은 시간을 잡아먹는지 다시 한번 확인할 수 있었다.

 

해결하는데 걸린 시간: 20분

 

출처 및 레퍼런스

문제 링크: 17352번: 여러분의 다리가 되어 드리겠습니다! (acmicpc.net)

 

관련 글

[자료구조 알고리즘/탐색 알고리즘(Search)] - [알고리즘] 합집합 찾기(Union-Find)

[온라인 코딩/탐색(Search)] - [백준] 1717번 집합의 표현

[온라인 코딩/탐색(Search)] - [구름 IDE] 비타 알고 시즌3 백신(★3)