[백준] 16562 친구비 - 유니온파인드(Union Find) + 최소조건(Minimum) JAVA

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

16562번: 친구비

코드설명

유니온파인드에 최소비용을 고려하는 문제입니다.

 

문제에서 고려해야할점은,

 

단순히 index가 작은 집합으로 집합을 합치는것이 아닌,

합쳤을때 금액이 작은 집합으로 합쳐야합니다.

public static void unionParent(int a, int b) {
    a = findParent(a);
    b = findParent(b);
 
    if( a != b) {
 
        if(money[a] < money[b]) parent[b] = a;
        else parent[a] = b;
 
    }
 
//		if( a < b ) parent[b] = a;
//		else parent[a] = b;
}

 

또한 금액이 낮은 기준으로 unionParent를 진행시켜서 낮은 금액 기준으로 rootParent가 되도록 설정하였을때

이후에 드는 금액을 찾기 위해서는, 해당 금액의 Index와 findParent(i) 가 같은지 확인하여 알아냅니다.

만약 index와 findParent(i)의 값이 같다면 해당 값이 rootParent, 즉 가장 금액이 작으면서 UnionParent를 한 Index입니다.

for(int i=1;i<=N;i++) {
    if(findParent(i) == i) {
        answer += money[i];
    }
}

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	
	public static int N, M, K;
	public static int answer = 0;
	public static int[] parent;
	public static int[] money;
	public static int[] friendA;
	public static int[] friendB;
	
	public static int findParent(int x) {
		if( x == parent[x]) return x;
		else return parent[x] = findParent(parent[x]);
	}
	
	public static void unionParent(int a, int b) {
		a = findParent(a);
		b = findParent(b);
		
		if( a != b) {
			
			if(money[a] < money[b]) parent[b] = a;
			else parent[a] = b;
			
		}
		
//		if( a < b ) parent[b] = a;
//		else parent[a] = b;
	}
	
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	K = Integer.parseInt(st.nextToken());
    	
    	parent = new int[N+1];
    	for(int i=0;i<N+1;i++) {
    		parent[i] = i;
    	}
    	
    	money = new int[N+1];
    	st = new StringTokenizer(br.readLine());
    	for(int i=1;i<=N;i++) {
    		money[i] = Integer.parseInt(st.nextToken());
    	}
    	
    	friendA = new int[M];
    	friendB = new int[M];
    	for(int i=0;i<M;i++) {
    		st = new StringTokenizer(br.readLine());
    		int a = Integer.parseInt(st.nextToken());
    		int b = Integer.parseInt(st.nextToken());
    		friendA[i] = a;
    		friendB[i] = b;
    		unionParent(a, b);
    	}
    	
    	for(int i=1;i<=N;i++) {
    		if(findParent(i) == i) {
    			answer += money[i];
    		}
    	}
    	
    	if(K < answer) System.out.println("Oh no");
    	else System.out.println(answer);
    	
    	
    }
    
    
}

 

처음에 최소비용을 고려하지 않고, unionParent를 한 코드입니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	
	public static int N, M, K;
	public static int answer = 0;
	public static int[] parent;
	public static int[] money;
	public static int[] friendA;
	public static int[] friendB;
	
	public static int findParent(int x) {
		if( x == parent[x]) return x;
		else return parent[x] = findParent(parent[x]);
	}
	
	public static void unionParent(int a, int b) {
		a = findParent(a);
		b = findParent(b);
		if( a < b ) parent[b] = a;
		else parent[a] = b;
	}
	
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	K = Integer.parseInt(st.nextToken());
    	
    	parent = new int[N+1];
    	for(int i=0;i<N+1;i++) {
    		parent[i] = i;
    	}
    	
    	money = new int[N+1];
    	st = new StringTokenizer(br.readLine());
    	for(int i=1;i<=N;i++) {
    		money[i] = Integer.parseInt(st.nextToken());
    	}
    	
    	friendA = new int[M];
    	friendB = new int[M];
    	for(int i=0;i<M;i++) {
    		st = new StringTokenizer(br.readLine());
    		int a = Integer.parseInt(st.nextToken());
    		int b = Integer.parseInt(st.nextToken());
    		friendA[i] = a;
    		friendB[i] = b;
    		unionParent(a, b);
    	}
    	
    	for(int i=1;i<=N;i++) {
    		if(findParent(0) != findParent(i)) {
    			unionParent(0, i);
    			answer += money[i];
    		}
    	}
    	
    	if(K < answer) System.out.println("Oh no");
    	else System.out.println(answer);
    	
    	
    }
    
}