[BOJ] 4792 레드 블루 스패닝 트리 (JAVA)

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

4792번: 레드 블루 스패닝 트리

1. 빨간색 간선과 파란색 간선을 나눠서 저장합니다.

2. 빨간색 간선을 우선으로 신장 트리를 구성해봅니다.

3. 파란색 간선을 우선으로 신장 트리를 구성해봅니다.

4. 2에서 필요했던 파란색 간선보다 K가 크거나 같고, 3에서 필요했던 파란색 간선보다 K가 작거나 같으면 1 아니면 0을 출력합니다.

 

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

public class Main {
	
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;
    static int N, M, K, redCnt, blueCnt;
    static int[] parent;
    static ArrayList<Line> red, blue;

    public static void main(String[] args) throws Exception {

        while(true) {

            st = new StringTokenizer(br.readLine(), " ");
            N = Integer.parseInt(st.nextToken()); // 정점 수
            M = Integer.parseInt(st.nextToken()); // 간선 수
            K = Integer.parseInt(st.nextToken()); // 파란 간선 수
            if(N == 0 && M == 0 && K == 0) break;
            red = new ArrayList<>();
            blue = new ArrayList<>();
            for (int i = 0; i < M; i++) {
                st = new StringTokenizer(br.readLine(), " ");
                char a = st.nextToken().charAt(0);
                int from = Integer.parseInt(st.nextToken());
                int to = Integer.parseInt(st.nextToken());
                if(a == 'R') red.add(new Line(from, to));
                else blue.add(new Line(from, to));
            } // end of input

            if(blue.size() < K) {
                sb.append("0\n");
                continue;
            }

            // 레드 우선 스패닝 트리 만들기
            make();
            redCnt = blueCnt = 0;

            for (Line r : red) {
                if(union(r.from, r.to) && ++redCnt == N - 1) break;
            }
            for (Line b : blue) {
                if(union(b.from, b.to) && ++blueCnt + redCnt == N - 1) break;
            }

            // 최소한의 파란색 간선을 이용한 스패닝 트리에서
            // 파란색 간선이 K개를 넘으면 가망이 없음
            if(K < blueCnt) {
                sb.append("0\n");
                continue;
            }

            // 블루 우선 스패닝 트리 만들기
            make();
            redCnt = blueCnt = 0;

            for (Line b : blue) {
                if(union(b.from, b.to) && ++blueCnt == N - 1) break;
            }
            for (Line r : red) {
                if(union(r.from, r.to) && ++redCnt + blueCnt == N - 1) break;
            }

            if(blueCnt < K) sb.append("0\n");
            else sb.append("1\n");

        }

        System.out.print(sb.toString());

    }

    static boolean union(int a, int b) {

        a = find(a);
        b = find(b);

        if(a == b) return false;

        if(a < b) parent[b] = a;
        else parent[a] = b;

        return true;

    }

    static int find(int a) {

        if(a == parent[a]) return a;

        return parent[a] = find(parent[a]);

    }

    static void make() {

        parent = new int[N + 1];

        for (int i = 1; i <= N; i++) {
            parent[i] = i;
        }

    }

    static class Line {

        int from, to;

        public Line(int from, int to) {
            this.from = from;
            this.to = to;
        }

    }

}