[백준] 15809: 전국시대 - JAVA

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

 

풀이

각 국가에 군대가 있고, 국가들은 동맹, 전쟁을 통해 군대에 변화가 생긴다.

 

동맹을 맺으면 두 국가를 연합하여 하나의 국가로 만든다. 군대의 수는 합쳐진다.

 

전쟁을 하면 두 국가가 전쟁을 하여 군대의 수가 적은 국가는 속국이되고, 군대의 수는 소모된다.

 

두 국가가 같은 집합에 속하는지 확인하기 위해 서로소 집합을 이용했다.

 

``` findSet(int x)``` 메소드를 통해 해당 국가의 루트 국가를 찾는다.

 

``` union(int p, int q)``` 두 국가 p와 q를 동맹으로 묶는다. 군대의 수가 많은 국가를 루트로 설정하고 군대의 수를 합쳤다.

 

``` battle(int p, int q)``` 두 국가 p와 q가 전쟁을 벌인다. 군대의 수가 많은 국가의 군대가 상대 국가의 군대 수만큼 소모되며, 군대 수가 같을 경우 두 국가 모두 소멸한다.

 

최종적으로 자신이 루트 국가인 국가들의 개수와 군대의 수들을 출력해주었다.

 

---

 

메모리: 43340KB
시간: 1176ms
언어: Java 11

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

public class Main {
    static int[] countries;
    static int[] troops;

    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());

        countries = new int[n + 1];
        troops = new int[n + 1];
        for (int i = 1; i < n + 1; i++) {
            countries[i] = i;
            troops[i] = Integer.parseInt(br.readLine());
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int o = Integer.parseInt(st.nextToken());
            int p = Integer.parseInt(st.nextToken());
            int q = Integer.parseInt(st.nextToken());

            if (o == 1) {
                union(p, q);
            } else {
                battle(p, q);
            }
        }

        int count = 0;
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 1; i < n + 1; i++) {
            if (countries[i] == i) {
                count++;
                list.add(troops[i]);
            }
        }
        Collections.sort(list);

        System.out.println(count);
        for (Integer troop : list) {
            System.out.print(troop + " ");
        }
    }

    private static void battle(int p, int q) {
        int px = findSet(p);
        int py = findSet(q);

        if (troops[px] > troops[py]) {
            countries[py] = px;
            troops[px] -= troops[py];
        } else if (troops[px] < troops[py]) {
            countries[px] = py;
            troops[py] -= troops[px];
        } else {
            countries[px] = countries[py] = -1;
            troops[px] = troops[py] = 0;
        }
    }

    private static void union(int p, int q) {
        int px = findSet(p);
        int py = findSet(q);

        if (troops[px] > troops[py]) {
            countries[py] = px;
            troops[px] += troops[py];
        } else {
            countries[px] = py;
            troops[py] += troops[px];
        }
    }

    private static int findSet(int x) {
        if (x == countries[x]) {
            return x;
        } else {
            countries[x] = findSet(countries[x]);
            return countries[x];
        }
    }

}