글 읽기 - 다른 MST 솔루션과 로직상 차이가 안 보이는데 틀립니다, 도와주세요ㅜㅜ

starlover27 2년 전 0

소스코드는 아래와 같습니다.

구글링으로 다른 소스코드들을 모두 확인하여 로직을 비교했는데도 다른 점 없이 틀리기만을 반복해 질문드립니다.ㅜㅜ

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.stream.IntStream;
import java.util.regex.Pattern;

class InputProcessor {
    public static int[] strToIntArr(String s){
        return Pattern.compile(" ").splitAsStream(s).mapToInt(Integer::parseInt).toArray();
    }
}

class KruskalEdgeIW implements Comparable<KruskalEdgeIW>{
    int v1, v2, w;

    public KruskalEdgeIW(int v1, int v2, int w) {
        this.v1 = v1;
        this.v2 = v2;
        this.w = w;
    }

    @Override
    public int compareTo(KruskalEdgeIW o) {
        return Integer.compare(w, o.w);
    }
}

class 레드블루스패닝트리_4792 {
    int V, BE;
    ArrayList<KruskalEdgeIW> edges;
    int[] parent;

    public 레드블루스패닝트리_4792(int v, int be, ArrayList<KruskalEdgeIW> edges) {
        V = v;
        BE = be;
        this.edges = edges;
    }

    int solve() {
        // 파란 간선이 최소로 들어가는 스패닝 트리 > 파란 간선의 개수
        int min = MST(new PriorityQueue<>(edges));
        if(min == -1) return 0; // 스패닝 트리 만들 수 없는 경우

        // 파란 간선이 최대로 들어가는 스패닝 트리 > 파란 간선의 개수
        PriorityQueue<KruskalEdgeIW> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
        maxHeap.addAll(edges);
        int max = MST(maxHeap);
        if(max == -1) return 0; // 스패닝 트리 만들 수 없는 경우

        return (max >= BE && BE >= min) ? 1 : 0; // 범위 내에 있는지 확인
    }

    int MST(PriorityQueue<KruskalEdgeIW> pq) {
        int cnt = 0; // MST를 구성하는 간선의 개수
        int bCnt = 0; // MST를 구성하는 파란색 간선의 개수

        parent = IntStream.rangeClosed(0, V).toArray();
        KruskalEdgeIW e;

        while(cnt < V - 1){
            if(pq.isEmpty()) return -1; // 스패닝트리를 만들 수 없는 경우

            e = pq.poll();

            if(!union(e.v1, e.v2)) continue; // 사이클이 생길 수 있는 경우 false 반환

            cnt++;
            if(e.w == 1) bCnt++;
        }
        return bCnt;
    }

    boolean union(int a, int b){
        int pA = find(a);
        int pB = find(b);

        if(pA == pB) return false;

        if(pA < pB) parent[pB] = pA;
        else parent[pA] = pB;

        return true;
    }

    int find(int a) {
        return parent[a] == a ? a : (parent[a] = find(parent[a]));
    }
}

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] tmp;
        int V, E, BE;

        char[] info;
        String s = br.readLine();

        ArrayList<KruskalEdgeIW> edges;
        StringBuilder stb = new StringBuilder();

        while(!s.equals("0 0 0")){
            tmp = InputProcessor.strToIntArr(s);
            V = tmp[0]; E = tmp[1]; BE = tmp[2];
            edges = new ArrayList<>();

            for (int e = 0; e < E; e++) {
                info = br.readLine().replace(" ", "").toCharArray();
                edges.add(new KruskalEdgeIW(info[1] - '0', info[2] - '0', info[0] == 'B' ? 1 : 0));
            }
            stb.append(new 레드블루스패닝트리_4792(V, BE, edges).solve()).append("\n");

            s = br.readLine();
        }
        System.out.print(stb);
    }
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

다른 MST 솔루션과 로직상 차이가 안 보이는데 틀립니다, 도와주세요ㅜㅜ

starlover27 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말