Algorithm/Baekjoon

[Algorithm/Baekjoon] ์—ฌ๋Ÿฌ๋ถ„์˜ ๋‹ค๋ฆฌ๊ฐ€ ๋˜์–ด ๋“œ๋ฆฌ๊ฒ ์Šต๋‹ˆ๋‹ค! - 17352 (G5/JAVA)

dpdms2148 2025. 1. 6. 20:58
728x90

๐Ÿ“‘๋ฌธ์ œ๋งํฌ

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

๐Ÿ’ป์ฝ”๋“œ

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

public class Main {
    static int N;
    static int[] parent;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        parent = new int[N + 1];
        for (int i = 0; i < N + 1; i++) {
            parent[i] = i;
        }

        for (int i = 0; i < N - 2; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            union(x, y);
        }

        int island1 = 0, island2 = 0;
        for (int i = 1; i < N + 1; i++) {
            int n = find(i);
            if (island1 == 0) {
                island1 = n; 
            } else if (island1 != n && island2 == 0) {
                island2 = n;
                break;
            }
        }

        System.out.print(island1 + " " + island2);
    }

    public static boolean union(int x, int y) {
        x = find(x); //x์˜ ๋ถ€๋ชจ๋…ธ๋“œ ์ฐพ๊ธฐ
        y = find(y); //y์˜ ๋ถ€๋ชจ๋…ธ๋“œ ์ฐพ๊ธฐ

        // ์ด๋ฏธ ๊ฐ™์€ ๊ทธ๋ž˜ํ”„์— ์†ํ•ด์žˆ์„ ๋•Œ false ๋ฐ˜ํ™˜
        if (x == y) return false;

        if (x <= y) parent[y] = x;
        else parent[x] = y;
        return true;
    }

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

 

728x90