[JAVA] BOJ(백준) - 친구비 - 16562

문제 내용

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

16562번: 친구비

19학번 이준석은 학생이 N명인 학교에 입학을 했다. 준석이는 입학을 맞아 모든 학생과 친구가 되고 싶어한다. 하지만 준석이는 평생 컴퓨터랑만 대화를 하며 살아왔기 때문에 사람과 말을 하는 법을 모른다. 그런 준석이에게도 희망이 있다. 바로 친구비다!

학생 i에게 Ai만큼의 돈을 주면 그 학생은 1달간 친구가 되어준다! 준석이에게는 총 k원의 돈이 있고 그 돈을 이용해서 친구를 사귀기로 했다. 막상 친구를 사귀다 보면 돈이 부족해질 것 같다는 생각을 하게 되었다. 그래서 준석이는 “친구의 친구는 친구다”를 이용하기로 했다.

준석이는 이제 모든 친구에게 돈을 주지 않아도 된다!

위와 같은 논리를 사용했을 때, 가장 적은 비용으로 모든 사람과 친구가 되는 방법을 구하라.

입력

첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다.

두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10,000, 1 ≤ i ≤ N)

다음 M개의 줄에는 숫자 v, w가 주어진다. 이것은 학생 v와 학생 w가 서로 친구라는 뜻이다.

출력

준석이가 모든 학생을 친구로 만들 수 있다면, 친구로 만드는데 드는 최소비용을 출력한다. 만약 친구를 다 사귈 수 없다면, “Oh no”(따옴표 제거)를 출력한다.

---

문제 접근 방법

Union - Find를 활용하면 쉽게 풀수 있는 문제이다.

입력 받는 수들을 보면 알겠지만 입력 받은 수가 생성하는 트리는 한개일 수도 있고, 두개일 수도 있고, 그 이상으로 여러개일 가능성도 존재한다.

이를 고려하면 결과적으로 여러개의 트리를 하나로 만드는 과정이 필요한데 이때 각 루트노의 비용을 통해 k를 갱신하고 최소비용의 합을 구해주면된다.

정리해보면 아래와 같다.

로직

1. 입력받은 친구 관계에 따라 트리 만들기
   union 함수를 구현해서 입력받은 관계 (1, 3) , (2, 4) , (5, 4) 를 이용해 트리를 만들어준다.
   이를 트리로 만들어 주면 배열에서 다음과 같이 나오게된다.
   

   i	1	2	3	4	5
   parents[i]	1	2	1	2	2

2. 최소비용 계산하기.
   위의 표를 봤을때 1~5번학생을 모두 준석이의 친구로 만들기 위해선 1번, 2번 학생으로 친구로 만들게 되면 최소비용으로 모두 준석이의 친구로 만들수 있다.
   즉, 1번과 2번 학생은 자식노드와 부모노드가 같은 루트노드이고 이런 루트노드들을 탐색해서
   각 루트노드의 비용을 갖고 있는돈 k와 비교하여 친구를 살수 있다면 answer에 친구를 살때 드는 비용을 하나씩 더해주면 된다.

주의할 점

1. union 함수
   union함수를 만들때 루트노드가 될수 있는 노드들 중 최소의 비용을 갖고있는 노드를 루트노드로 만들어줘야 한다.
   (그래야 최소비용으로 친구를 만들수 있기때문)
   

   

참고

이번 문제는 Union-Find 알고리즘을 알고있다는 전제하에 설명했다.
만약 해당 알고리즘이 뭔지 잘 모르겠다면 아래문제에 자세히 설명돼있으니 먼저 풀어보고 오자.

https://record-developer.tistory.com/86

[JAVA] BOJ(백준) - 집합의 표현 - 1717

---

풀이

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

public class Main {
	static int[] parents; //parents[자식노드] = 부모노드
	static int[] money;
	static int answer = 0;
	static int k;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		
		int n = Integer.parseInt(st.nextToken());//학생 수
		int m = Integer.parseInt(st.nextToken());//친구 관계 수
		k = Integer.parseInt(st.nextToken());//갖고있는 돈
	
		parents = new int[n+1];
		for(int i=1; i<=n; i++) //배열 초기화
			parents[i] = i;
		
		st = new StringTokenizer(br.readLine());
		money = new int[n+1];
		for(int i=1; i<=n; i++) //각 학생의 친구비용
			money[i] = Integer.parseInt(st.nextToken());
		
		for(int i=0; i<m; i++) { //친구 관계에 따른 트리만들기(union)
			st = new StringTokenizer(br.readLine());
			int v = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			union(v,w);
		}
		
		//cost함수를 통해 최소비용 계산
		if(cost(n)) System.out.println(answer);
		else System.out.println("Oh no");
		
	}
	
	//합치기 - 트리 만들기 - 같은 루트노드 같도록 만들기
	public static void union(int v1, int v2) {
		v1 = find(v1);//v1의 루트 노드 찾기
		v2 = find(v2);//v2의 루트 노드 찾기
		
		if(v1 != v2) {
			 //루트 노드가 다를때 합치기전에 최소비용이
			 //들어가는 노드를 루트노드로 해서 합치기
			if(money[v1] > money[v2]) parents[v1] = v2; //v2를 루트노드로
			else parents[v2] = v1; //v1을 루트노드로
		}
	}
	
	//루트노드 찾기
	public static int find(int v) {
		//자식과 부모노드가 같다면 v가 루트노드임.
		if(parents[v]==v) return v; 
		
		//다를땐 재귀를 통해서 v노드의 루트노드 찾기
		return parents[v] = find(parents[v]);
	}
	
	//비용 얼마나 드는지 계산(계산되면 true, 안되면 false반환)
	public static boolean cost(int n) {
		//1~n까지 루트노드를 탐색
		for(int i=1; i<=n; i++) {
			if(parents[i]==i) {//루트노드 일때
				k -= money[i];//갖고있는 돈에서 친구비용 빼기
				if(k>=0) answer += money[i];//answer에 합칠 친구 비용 추가.
				else return false;//돈없으면 false 반환
			}
		}
		return true;
	}
}

---

마치며

Union-Find 알고리즘에서 union 부분을 조금 응용한 문제인데 크게 어렵지 않았던 문제이다.

하지만 문제를 읽고 먼저 문제를 Union-Find 방식으로 풀지 다른 방식으로 풀지 판단하기 위해선 좀더 많은 경험이 필요하다 생각한다.