글 읽기 - MST 프림으로 풀었는데, 어느 부분이 틀린지 모르겠네요...

jyyoon0615 1년 전 0

게시판 글이나 구글링을 했지만 틀린부분을 찾을 수가 없었습니다.

수정해야 할 부분이나 테스트케이스들이 있다면 말씀해주시면 정말 감사드립니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;

public class Main {
    static ArrayList<ArrayList<Node>> graph;
    static class Node {
        String gender;
        int to;
        int weight;

        public Node(String gender, int to, int weight) {
            this.gender = gender;
            this.to = to;
            this.weight = weight;
        }
    }

    public static void prim(int n, int m, String startGender, int startVertex) {
        int weightSum = 0;
        boolean[] visited = new boolean[n + 1];
        PriorityQueue<Node> pq = new PriorityQueue<>((x, y) -> x.weight - y.weight);
        pq.offer(new Node(startGender, startVertex, 0)); // 시작 시 맨 처음 제시된 노드에서 시작하도록

        int cnt = 0; // 간선 개수
        while(!pq.isEmpty()) {
            Node cur = pq.poll();
            if(visited[cur.to]) {
                continue;
            }

            weightSum += cur.weight;
            visited[cur.to] = true;
            cnt++;

            if(cnt == n) {
                break;
            }

            for (int i = 0; i < graph.get(cur.to).size(); i++) {
                Node adj = graph.get(cur.to).get(i);
                if(visited[adj.to] /*|| adj.gender.equals(cur.gender)*/) { // 이 부분은 리스트 만들 때 빼고 받아서 지웠습니다
                    continue;
                }
                pq.offer(new Node(adj.gender, adj.to, adj.weight));
            }
        }

        if(cnt == n) {
            System.out.println(weightSum);
        } else {
            System.out.println("-1");
        }

    }

    public static void main(String[] args) throws IOException {
        graph = new ArrayList<>();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        int n = Integer.parseInt(s[0]);
        int m = Integer.parseInt(s[1]);
        String[] s2 = br.readLine().split(" ");
        String startGender = s2[0]; // 시작할 때 사용할 성별
        int startVertex = 0; // 시작할 때 사용할 노드
        for (int i = 0; i < n + 1; i++) {
            graph.add(new ArrayList<>());
        }
        for (int i = 0; i < m; i++) {
            String[] s3 = br.readLine().split(" ");
            int from = Integer.parseInt(s3[0]);
            int to = Integer.parseInt(s3[1]);
            int weight = Integer.parseInt(s3[2]);
            if(s2[to-1].equals(s2[from-1])) { // 성별이 같으면 리스트에 넣지 않기
                continue;
            }
            graph.get(from).add(new Node(s2[to - 1], to, weight));
            graph.get(to).add(new Node(s2[from - 1], from, weight));
            if(i == 0) {
                startVertex = from;
            }
        }
        prim(n, m, startGender, startVertex);
    }
}

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

문제

문제

출처

ICPC

MST 프림으로 풀었는데, 어느 부분이 틀린지 모르겠네요...

jyyoon0615 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말