[백준 16402] 제국 - Java 문제풀이

문제 링크: https://www.acmicpc.net/problem/16402

16402번: 제국

 

문제

배성일력 73년, 대륙을 주름잡던 성일 제국은 무리한 정복 전쟁 끝에 멸망하게 되었다. 기회를 노리던 반란군들은 혼란을 틈타 제각각 왕국을 선포했고, 왕국들은 제국의 자리를 차지하기 위해 수많은 전쟁을 치르게 되었다.

전쟁은 다음과 같은 방식으로 진행된다.

다른 왕국의 속국이 아닌 왕국은 자신의 속국이 아닌 다른 왕국을 공격하여 전쟁을 벌일 수 있다. 만약 전쟁에서 승리한다면 그 왕국과 그 왕국의 속국들을 전부 자신의 속국으로 삼게 된다. 때로는 다른 왕국의 속국을 공격하는 경우도 있는데, 이 경우 그 왕국의 종주국(그 왕국을 거느린 왕국)은 그 왕국을 지키기 위해 지원을 아끼지 않는다. 따라서 여기서 승리한다면 빈털터리가 된 종주국과 그 속국들까지도 전부 자신의 속국으로 삼을 수 있다. 그러나 전쟁에서 패배한다면 자신과 자신의 속국들이 전부 상대 왕국(만약 다른 왕국의 속국이라면 그 종주국)의 속국으로 넘어가게 된다.

속국은 기본적으로 다른 왕국을 공격할 수 없지만, 한 가지 예외가 있다. 바로 자신의 종주국을 공격하는 것이다. 만약 이 전쟁에서 속국이 승리한다면 속국 신세에서 벗어나 종주국이었던 왕국과 그 속국들을 속국으로 삼게 된다. 그러나 종주국이 승리한다면 아쉽게도 아무 일도 일어나지 않는다.

왕국들의 이름과 두 왕국의 전쟁 결과들이 주어질 때, 모든 전쟁이 끝난 후 속국이 아닌 왕국들의 수와 속국이 아닌 각 왕국의 이름을 출력하라.

 

입력

첫째 줄에 왕국들의 수 N(2 ≤ N ≤ 500), 전쟁 결과의 수 M(1 ≤ M ≤ 2,000) 이 주어진다.

둘째 줄부터 N개의 줄에 걸쳐 각 왕국의 이름이 주어진다.

왕국의 이름은 항상 “Kingdom of ”로 시작하며, 그 뒤로 공백 없는 하나의 단어로 이루어진다. 왕국 이름은 알파벳 대소문자와 공백으로만 이루어지고, 이름의 총 길이는 공백을 포함해 20을 넘지 않는다. 또한 왕국의 이름은 중복되지 않는다.

그다음 줄부터 M개의 줄에 걸쳐 전쟁의 결과가 주어진다.

전쟁의 결과로 왕국1의 이름, 왕국2의 이름, w(w = 1 or 2)가 공백 없이 쉼표(,)를 사이에 둔 형식으로 주어지며, w가 1인 경우 왕국1이, 2인 경우 왕국2가 승리했다는 것을 뜻한다. 왕국 이름의 입력 순서는 어느 쪽이 먼저 공격했는지와는 관계가 없으며, 문제 조건에 따라 성립할 수 있는 전쟁만이 입력으로 주어진다.

 

출력

첫째 줄에 속국이 아닌 왕국의 수를 출력한다.

둘째 줄부터 속국이 아닌 왕국의 이름을 ASCII 사전 순으로 정렬하여 한 줄에 하나씩 출력한다.

풀이

접근법

1. 제국 입력은 공백(" ")을 기준으로 2번째 껄 하면 되겠다.
2. 전쟁 결과는 먼저 쉼표(,)를 기준으로 나눈 후, 제국 입력때와 같이 공백을 기준으로 2번째껄 이용해 파싱하면 될 것 같다.
3. 종주국과 속국이 있으니까 유니온 파인드를 이용하면 될 것 같다.
   1. 만약 다른 왕국끼리 싸우는 전쟁에서는 이긴 왕국이 루트가 되도록
   2. 만약 종주국과 속국이 싸우는 전쟁에서는 이기는 쪽이 루트가 되도록 하면 될 것 같다.

 

코드

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

public class Main {
    private static int[] parents;
    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());
        parents = new int[N+1];
        for(int i=0;i<=N;i++) parents[i] = i;
        Map<String, Integer> map = new TreeMap<>();
        String[] names = new String[N+1];
        String[] strs;
        for(int i=1;i<=N;i++) {
        // 1. 제국 입력은 공백(" ")을 기준으로 2번째 껄 하면 되겠다.
            strs = br.readLine().split(" ");
            map.put(strs[2], i);
            names[i] = strs[2];
        }
        for(int m=0;m<M;m++) {
	    // 2. 전쟁 결과는 먼저 쉼표(,)를 기준으로 나눈 후, 
            // 제국 입력때와 같이 공백을 기준으로 2번째껄 이용해 파싱하면 될 것 같다.
            strs = br.readLine().split(",");
            int k1 = map.get(strs[0].split(" ")[2]);
            int k2 = map.get(strs[1].split(" ")[2]);
            int result = strs[2].charAt(0) - '0';
            // 항상 이기는 쪽이 앞에 오도록 설정
            if (result == 1) union(k1, k2);
            else union(k2, k1);
        }

        PriorityQueue<String> pq = new PriorityQueue<>();
        for(int i=1;i<=N;i++) {
            if (parents[i] == i) pq.add(names[i]);
        }
        StringBuilder sb = new StringBuilder();
        sb.append(pq.size()).append("\n");
        while(!pq.isEmpty()) {
            sb.append("Kingdom of ").append(pq.poll()).append("\n");
        }
        System.out.println(sb);
    }


    // 3. 종주국과 속국이 있으니까 유니온 파인드를 이용하면 될 것 같다.
    private static int findset(int x) {
        if (parents[x] == x) return x;
        else return parents[x] = findset(parents[x]);
    }

    private static void union(int x, int y) {
        int xr = findset(x);
        int yr = findset(y);

        // 3-1. 만약 종주국과 속국이 싸우는 전쟁에서는 이기는 쪽이 루트가 되도록 하면 될 것 같다.
        if(xr == yr) {
            parents[x] = x;
            parents[y] = x;
            return ;
        }
        // 3-2. 만약 다른 왕국끼리 싸우는 전쟁에서는 이긴 왕국이 루트가 되도록
        parents[yr] = xr;
    }
}

 

26분 걸렸다 .. ㅎ