[알고리즘] 백준 17352 여러분의 다리가 되어 드리겠습니다! - 유니온파인드 - 자바, 코틀린

 

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

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

 

 

 

 

백준 17352 유니온파인드 유형의 문제를 풀어봤습니다. ㅎㅎ

유니온파인드의 기본적인 원리를 사용하면 되는 문제입니다.

 

다리가 있는 섬들을 Union 해준 후

다리가 안이어진 도시들을 출력해주면 끝입니다!

 

풀이는 다음과 같습니다.

 

[Java]

import java.util.Scanner;

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

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        parent = new int[N + 1];
        // 1, 초기화
        for (int i = 1; i <= N; i++) {
            parent[i] = i;
        }
        // 2. 유니온
        for (int i = 0; i < N - 2; i++) {
            int start = sc.nextInt();
            int end = sc.nextInt();
            union(start, end);
        }
        // 3. 다리 체크 및 이어주기
        for (int i = 2; i <= N; i++) {
            if (!isSameParent(1, i)) {
                System.out.print(1 + " " + i);
                return;
            }
        }
    }

    private static void union(int x, int y) {
        x = find(x);
        y = find(y);
        if (x != y) {
            if (x < y) parent[y] = x;
            else parent[x] = y;
        }
    }

    private static boolean isSameParent(int x, int y) {
        return find(x) == find(y);
    }

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

 

[Kotlin]

import java.util.*


private var N = 0
private lateinit var parent: IntArray
fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    N = sc.nextInt()
    parent = IntArray(N + 1)
    // 1, 초기화
    for (i in 1..N) {
        parent[i] = i
    }
    // 2. 유니온
    for (i in 0 until N - 2) {
        val start = sc.nextInt()
        val end = sc.nextInt()
        union(start, end)
    }
    // 3. 다리 체크 및 이어주기
    for (i in 2..N) {
        if (!isSameParent(1, i)) {
            print("1 $i")
            return
        }
    }
}

private fun union(x: Int, y: Int) {
    var x = x
    var y = y
    x = find(x)
    y = find(y)
    if (x != y) {
        if (x < y) parent[y] = x else parent[x] = y
    }
}

private fun isSameParent(x: Int, y: Int): Boolean {
    return find(x) == find(y)
}

private fun find(x: Int): Int {
    return if (parent[x] == x) {
        x
    } else {
        find(parent[x]).also { parent[x] = it }
    }
}

 

 

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!