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

문제

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

리뷰

유니온 파인드를 이용하여 풀이할 수 있는 간단한 문제였다.

입력으로 들어오는 N-2개의 관계에 포함되는 섬들을 union 연산을 통하여 같은 루트로
설정해준뒤 서로 다른 루트를 가지는 두 개의 노드만 임의로 찾아서 출력해주는 식으로
로직을 구성하였다. 해당 두 노드만 parent 배열의 값을 최적화된 유니온 파인드 로직에서
음수값을 가지므로 이 점을 이용하여 탐색하면 되었다.

로직의 시간복잡도는 입력을 받으면 union 연산을 수행하는 부분의 $O(N(a(N))$으로 수렴하고
이는 최악의 경우인 $N=300,000$일때도 제한 조건인 1초를 무난히 통과한다.

코드

import java.util.Arrays;
import java.util.Scanner;
import java.util.StringTokenizer;

import static java.lang.Integer.parseInt;

public class Main {
    static int[] parent;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = parseInt(in.nextLine());

        parent = new int[N + 1];
        Arrays.fill(parent, -1);

        StringTokenizer st;

        for (int i = 0; i < N - 2; i++) { // O(N(a(N))
            st = new StringTokenizer(in.nextLine());
            int u = parseInt(st.nextToken());
            int v = parseInt(st.nextToken());

            union(u, v);
        }

        int[] node = {1, 2};
        int idx = 0;

        for (int i = 1; i < parent.length; i++) { // O(N)
            if (parent[i] < 0)
                node[idx++] = i;

            if (idx == 2) break;
        }

        System.out.print(node[0] + " " + node[1]);
        in.close();
    }

    static int find(int u) {
        if (parent[u] < 0) return u;

        return parent[u] = find(parent[u]);
    }

    static void union(int u, int v) {
        int r1 = find(u);
        int r2 = find(v);

        if (r1 == r2) return;

        if (parent[r1] < parent[r2]) {
            parent[r1] += parent[r2];
            parent[r2] = r1;
        } else {
            parent[r2] += parent[r1];
            parent[r1] = r2;
        }
    }
}

결과