섬 연결하기

섬 연결하기

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

import java.util. * ; class Solution { private static int [] parent; // 부모 설정 public static void Union( int a, int b){ a = Find(a); b = Find(b); if (a > b) { parent[a] = b; } else { parent[b] = a; } } // 부모 찾기 public static int Find( int x) { if (parent[x] = = x) return x; else return Find(parent[x]); } public int solution( int n, int [][] costs) { int answer = 0 ; parent = new int [n]; //부모 초기화 for ( int i = 0 ;i < n;i + + ){ parent[i] = i; } // 비용 오름차순 정렬 Arrays.sort(costs, new Comparator < int [] > () { @Override public int compare( int [] o1, int [] o2){ return o1[ 2 ] - o2[ 2 ]; } }); for ( int i = 0 ;i < costs. length ;i + + ){ int a = costs[i][ 0 ]; int b = costs[i][ 1 ]; // 사이클이 생기지 않을 경우 if (Find(a) ! = Find(b)){ Union(a, b); answer + = costs[i][ 2 ]; } } return answer; } } Colored by Color Scripter

from http://zzunsik.tistory.com/199 by ccl(A) rewrite - 2021-09-15 00:01:13