[알고리즘] 백준 1717 집합의 표현 -유니온파인드(Union-find)- 자바

[알고리즘] 백준 1717 집합의 표현 -유니온파인드(Union-find)- 자바

300x250

SMALL

www.acmicpc.net/problem/1717

백준 유니온파인드 단계별풀기의 문제입니다.

처음 푸는 유형이라 밑을 참고해서 공부 후 풀었습니다.

brenden.tistory.com/34

풀이는 다음과 같습니다.

[Java]

import java.util.Scanner; class Main { private static int[] parent; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); parent = new int[n + 1]; // [해당노드] = 최상위부모값 for (int i = 1; i <= n; i++) { //Disjoint-set 만들어줌(상호배타적집합) parent[i] = i; } for (int i = 0; i < m; i++) { int flag = sc.nextInt(); int a = sc.nextInt(); int b = sc.nextInt(); if (flag == 0) { union(a, b); } else { if(isSameParent(a,b)){ System.out.println("YES"); }else { System.out.println("NO"); } } } } private static boolean isSameParent(int x, int y) { x = find(x); y = find(y); return x == y; } 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 int find(int x) { //최상위 부모값을 찾는다 if (x == parent[x]) { return x; } else { return parent[x] = find(parent[x]); } } }

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

300x250

LIST

from http://youngest-programming.tistory.com/427 by ccl(S) rewrite - 2021-10-28 02:26:39