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

• 문제: https://www.acmicpc.net/problem/17352
• 분류: Union-find
• 난이도: G5
• 소요시간: 10m
• 자아성찰:
  • 유니온 파인드 구현 연습 차 풀어보았다.
  • 유니온 파인드의 원리가 생각보다 이해하기 쉬웠어서 union(), find() 메서드를 금방 떠올려 낼 수 있었다.
  • 이래서 이해 >>>> 단순 암기라고 하는 것 같다.
  • N-2개 다리 = 무조건 2개 그룹으로 나누어진다 = 1번 섬과 이어지지 않은 하나의 섬을 찾아서 이어주면 끝이다
    • 시간복잡도는 O(N)
    • find의 경우 경로 압축(parent[a] = find(parent[a])) 을 통해 find 시 parent를 업데이트 하도록 하면 시간복잡도는 상수로 처리된다.

17352번: 여러분의 다리가 되어 드리겠습니다!

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class B_17352 {

    public static int[] parent;
    public static int N;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        parent = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            parent[i] = i;
        }
        for (int i = 0; i < N - 2; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            union(a, b);
        }
        int targetParent = find(1);
        for (int i = 2; i <= N; i++) {
            // N - 2개 다리가 존재하므로 연결된 그룹은 무조건 2개로 나누어짐
            // 1번 섬은 무조건 2개 그룹 중 하나의 그룹에 속해있음
            // 1번 섬과 연결되지 않은 섬을 이어주면 모든 섬이 연결됨
            if (targetParent != find(i)) {
                System.out.println(1 + " " + i);
                break;
            }
        }
    }

    public static void union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a != b) {
            if (a < b) parent[b] = a;
            else parent[a] = b;
        }
    }

    public static int find(int a) {
        if (a == parent[a]) return a;
        return parent[a] = find(parent[a]);
    }
}