백준 15809 전국시대

 

package algostudy10_BOJ_15809;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Review {
	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());
		
		int country[][] = new int[n+1][2];
		for(int i = 1 ; i <= n ;i++) {
			country[i][0] = i;
			country[i][1] = Integer.parseInt(br.readLine());
		}
		
		// 1이면 동맹 2이면 전쟁
		for(int i = 0 ; i < m ; i++) {
			String order[] = br.readLine().split(" ");
			
			int option = Integer.parseInt(order[0]);
			int a = Integer.parseInt(order[1]);
			int b = Integer.parseInt(order[2]);
			
			if(option == 1) {
				union(country, a, b);
			}else {
				war(country, a, b);
			}
		}
		HashSet<Integer> set = new HashSet<Integer>();
		for(int i = 1 ; i < country.length;i++) {                      
			
			if(getParent(country, i)!=0) {
				set.add(getParent(country, i) );
			}

		}
		ArrayList<Integer> list = new ArrayList<Integer>();
		
		for(int num:set) {
			list.add(country[num][1]);
		}
		
		list.sort(new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				// TODO Auto-generated method stub
				return o1 - o2;
			}
		});
		
		System.out.println(list.size());
		
		
		for(int num : list) {
			System.out.print(num+" ");
		}

	}
	
	public static int getParent(int country[][],int a) {
		if(country[a][0] == a) {
			return a;
		}else {
			return getParent(country,country[a][0]);
		}
	}
	
	public static void union(int country[][],int a,int b) {
		a = getParent(country, a);
		b = getParent(country, b);
		
		
		if(a<b) {
			country[b][0] = a;
			country[a][1] +=country[b][1];
			country[b][1] = country[a][1];
		}else {
			country[a][0] = b;
			country[b][1] +=country[a][1];
			country[a][1] = country[b][1];
		}

	}
	public static void war(int country[][],int a,int b) {
		a = getParent(country, a);
		b = getParent(country, b);
		
		if(a !=b) {
			
			if(country[a][1] <country[b][1]) {
				country[a][0] =b;
				country[b][1] -= country[a][1];
			}else if(country[a][1] >country[b][1]){
				country[b][0] = a;
				country[a][1] -= country[b][1];
			}else {
				country[a][0] =0;
				country[b][0] =0;
			}
		}
	}
	
	
}

 

풀이 방법

국가의 번호와 병력을 2차원 배열에 저장한다.

 

주어진 수가 1일 경우 동맹임으로

getParent 함수를 이용해 부모(동맹)의 번호를 가져와 union하고 병력의 수를 더해준다.

 

주어진 수가 2일 경우 전쟁임으로

getParent함수를 이용해 부모(동맹)의 병력을 가져와 어느 국가의 병력이 더 많은지 평가한다.

평가후 적은 병력을 가진 국가의 번호는 상대국가 번호로 지정하여 속국처리

살아남은 국가의 병력은 상대국가의 병력을 빼준 값으로 초기화한다.

 

처음에 병력만 set에 넣어 중복처리를 하려 했으나

다른 국가인데 병령이 같을 수 있다는 사실을 인지 못해 조금 해매었다.