[백준 / JAVA] 친구비 - 16562

문제

풀이

입력 : 학생 수 N, 친구 관계 수 M, 가지고 있는 돈 k가 주어진다.

두번째 줄 부터 학생 N의 학생이 원하는 친구비 An 이 주어진다.

M개의 친구 관계가 주어진다.

 

M개의 친구 관계를 이용하여 서로 친구 관계인 집합을 구합니다.

유니온 파인드를 이용하였는데 배열 내에서 같은 값(친구 관계 중에서 가장 낮은 번호)을 가지면

친구 관계이므로, 이 들중에서 가장 적은 친구비를 총합에 더합니다.

모든 집합에서 한 명씩 친구비를 구하여 초기에 주어진 k와 비교하여 결과를 출력합니다.

 

코드

import java.io.*;
import java.util.*;
import java.math.*;

class Main {
	static int arr[];
	static int find(int x) {
		if(arr[x] == x)
			return x;
		else return arr[x] = find(arr[x]);
	}
          public static void main(String[] args) throws IOException{        	        	         	         	      	   
        	  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
              BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
              StringTokenizer st = new StringTokenizer(br.readLine());
              int n = Integer.parseInt(st.nextToken());
              int m = Integer.parseInt(st.nextToken());
              int total = Integer.parseInt(st.nextToken());
              int money[] = new int [n+1];
              st = new StringTokenizer(br.readLine());
              for(int i=1;i<n+1;i++) {
            	  money[i] = Integer.parseInt(st.nextToken());
              }
              arr = new int[n+1];
              for(int i=1;i<n+1;i++) {
            	  arr[i] = i;
              }
              int chk=0;
              for(int i=1;i<m+1;i++) {
            	  st = new StringTokenizer(br.readLine());
            	  int a = find(Integer.parseInt(st.nextToken()));
            	  int b = find(Integer.parseInt(st.nextToken()));
            	  
            	  if(a<b) {
            		  arr[b] = a;
            	  }
            	  else if(a>b) {
            		  arr[a] = b;
            	  }
              }
              boolean visit[] = new boolean[n+1];
              int temp =0;
              for(int i=1;i<n+1;i++) {
            	  if(!visit[find(i)]) {
            		  temp+=money[find(i)];
            		  visit[find(i)]=true;
            	  }
            	  else {
            		  if(money[i]<money[find(i)]) {
            			  temp+=money[i];
            			  temp-=money[find(i)];
            			  money[find(i)]=money[i];
            		  }
            	  }
              }
              if(temp<=total) {
            	  bw.write(String.valueOf(temp));
              }
              else
            	  bw.write("Oh no");
              
              
              
              bw.flush();
                     
    }
}

결과