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

문제

선린월드에는 N개의 섬이 있다. 섬에는 1, 2, ..., N의 번호가 하나씩 붙어 있다. 그 섬들을 N - 1개의 다리가 잇고 있으며, 어떤 두 섬 사이든 다리로 왕복할 수 있다.

어제까지는 그랬다.

"왜 다리가 N - 1개밖에 없냐, 통행하기 불편하다"며 선린월드에 불만을 갖던 욱제가 다리 하나를 무너뜨렸다! 안 그래도 불편한 통행이 더 불편해졌다. 서로 왕복할 수 없는 섬들이 생겼기 때문이다. 일단 급한 대로 정부는 선린월드의 건축가를 고용해, 서로 다른 두 섬을 다리로 이어서 다시 어떤 두 섬 사이든 왕복할 수 있게 하라는 지시를 내렸다.

그런데 그 건축가가 당신이다! 안 그래도 천하제일 코딩대회에 참가하느라 바쁜데...

입력

첫 줄에 정수 N이 주어진다. (2 ≤ N ≤ 300,000)

그 다음 N - 2개의 줄에는 욱제가 무너뜨리지 않은 다리들이 잇는 두 섬의 번호가 주어진다.

출력

다리로 이을 두 섬의 번호를 출력한다. 여러 가지 방법이 있을 경우 그 중 아무거나 한 방법만 출력한다.

https://www.acmicpc.net/problem/17352

풀이

간단한 DSU 즉 Disjoint Set Union 문제로, 서로 배타적인 두 집합을 구현한뒤, 1이 포함되지않은 다른 집합의 원소를 1과 이어주도록 출력하면 된다.

관련 알고리즘 >> https://velog.io/@cldhfleks2/Algorithm-DSU-Disjoint-Set-UnionFind

1. 입력받는 부분
   
   Parent 배열은 '인덱스=원소, 값=부모노드의 원소번호'를 나타낸다. DSU에 사용될 배열.
2. DSU - Find
   
   원소 x의 루트 노드를 리턴한다. 이때 경로압축을 하는 코드를 넣어서 이때 탐색한 모든 원소가 루트노드를 부모노드로 가리키게되어, 다시 Find할때의 시간복잡도를 줄여준다.
3. DSU - Union
   
   위의 1번과정에서 입력의 2번째줄부터 받은 정보로, 각 원소를 집합으로 묶는다. 이때 기존의 트리가 있다면 해당 트리에 Union 연산을 하게되는것 이다.
4. 두 다리가 연결 되있는지 확인하는 부분
   문제의 핵심부분으로 연결되있지 않은 다리를 찾아서
   
   이와 같이 1번 다리와 연결함을 출력하면 된다.

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>
int n;
int *parent; //각원소 x에대한 부모노드를 나타내는 배열
void logic();
void init();
bool isConnect(int x, int y);
int getParent(int x);

int getParent(int x) { //원소x의 루트노드를 리턴
    if (parent[x] == x) //
        return x;
    //return find(parent[x]) : 기본형태
    return parent[x] = getParent(parent[x]); //경로압축하며 리턴
}

void buildBridges(int x, int y) { //다리를 연결하는 함수
    //x, y원소의 부모노드 번호를 찾아서 x, y에 대입
    x = getParent(x);
    y = getParent(y);
    if (x == y) //부모노드가 같다 = 같은 집합 = 다리가 연결되있다.
        return; //연결되있다면 중단
    //연결 되있지않으면 연결시킴. (부모노드의 자식노드로 대입시킴)
    parent[y] = x;
}

bool isConnect(int x, int y) { //다리가 연결 되있는가?
    //x, y 원소의 부모노드번호를 찾아서 다시 x, y에 대입 
    x = getParent(x);
    y = getParent(y);
    if (x == y) //서로 부모노드가 같은가? = 같은 집합인가? = 다리로 연결되있다.
        return true; //연결되있음(합연산이 되었음)
    return false; 
}

void init() {
    scanf("%d", &n);
    parent = new int[n + 1];
    for (int i = 0; i <= n; i++) //노드 설정
        parent[i] = i;

    for (int i = 0; i < n - 2; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        buildBridges(x, y);
    }
}

void logic() {
    for (int i = 2; i <= n; i++) {
        if (!isConnect(1, i)) { //연결 되지않은 다리 번호 i를 탐색
            printf("1 %d", i); //1번과 연결하면 모든 다리가 연결된것.(문제 핵심)
            return;  //종료
        }
    }
}

int main(void) {
    init();
    logic();

    return 0;
}