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

 

문제 간단 정리

'' 생략

문제 해결 방법

이 문제는 섬과 섬 사이의 연결 관계를 파악해야 하는 그래프 관련 문제입니다. 이를 효율적으로 파악하기 위해 Union-Find 알고리즘을 사용합니다.

Union-Find는 그래프의 연결 요소를 식별하고 관리하기 위한 알고리즘입니다. Union-Find 알고리즘에서 'union' 연산은 두 집합을 하나로 합치고, 'find' 연산은 특정 원소가 어떤 집합에 속하는지를 찾는 데 사용됩니다.

본 문제에서는 다리 하나가 무너져 서로 왕복할 수 없는 섬들이 생겼습니다. 이때 두 섬을 다시 다리로 이어서 모든 섬이 왕복 가능하도록 해야 합니다. 이를 위해 먼저 주어진 섬 간 연결 정보를 이용해 각 섬의 부모 노드 정보를 업데이트합니다. 이렇게 하면 어떤 섬이 어떤 섬과 연결되어 있는지를 빠르게 알 수 있습니다.

Union-Find 알고리즘을 적용한 코드는 다음과 같습니다.

전체 코드

#include <iostream>
#include <vector>
using namespace std;
int n, m;
int parent[1000001];

int getParent(int x) {
    if (parent[x] == x) return x;
    return parent[x] = getParent(parent[x]);
}

void unionParent(int a, int b) {
    a = getParent(a);
    b = getParent(b);
    if (a > b) parent[a] = b;
    else parent[b] = a;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin.tie(NULL);

    

    int N;
    cin >> N;

    for (int i = 1; i <= N; i++) {
        parent[i] = i;
    }

    for (int i = 1; i <= N - 2; i++) {
        int a, b;
        cin >> a >> b;
        unionParent(a, b);
       
    }
    for (int i2 = 1; i2 <= N - 1; i2++) {
        int A = i2;
        for (int j = i2 + 1; j <= N; j++) {
            int B = j;
            A = getParent(A);
            B = getParent(B);
            if (A != B) {
                cout << A << " " << B;
                return 0;
            }

        }
    }
    

    return 0;

    
}