글 읽기 - 어떤 조건을 빼먹은걸까요?

gray22 3년 전 0

MST 문제여서 Prim으로 풀어봤는데 어디서 문제인지를 못찾겠습니다.

어떤 함정을 피하지 못한걸까요. 아니면 코드가 잘못된걸까요?

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder output = new StringBuilder();
    static StringTokenizer tokens;

    static int N;
    static int[][] graph;
    static boolean[] visited;
    static long cost = 0;
    static PriorityQueue<Vertex> pq = new PriorityQueue<>();
    static int newBridges;

    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(input.readLine());
        graph = new int[N][N];
        // 이미 연결된 지점들은 0의 비용으로 pq에 넣어주자. 이들이 출발점
        for (int r = 0; r < N; r++) {
            tokens = new StringTokenizer(input.readLine(), " ");
            for (int c = 0; c < N; c++) {
                graph[r][c] = Integer.parseInt(tokens.nextToken());
                if (graph[r][c] < 0) {
                    cost -= graph[r][c];
                    graph[r][c] = 0;
                    pq.offer(new Vertex(r, 0, c));
                }
            }
        }
        // 양방향 이었으므로 /2 처리
        cost = cost / 2;
        //System.out.println(pq);
        prim();
        output.insert(0, cost + " " + newBridges + "\n");
        System.out.println(output);
    }

    static void prim() {
        boolean[] visited = new boolean[N];

        // 만약 비어있을 경우는 임의의 점에서 시작
        if (pq.isEmpty()) {
            pq.offer(new Vertex(0, 0, 0));
        }
        int checked = 0;
        while (!pq.isEmpty()) {
            Vertex head = pq.poll();

            // 사용하기
            if (visited[head.i]) {
                continue;
            }
            visited[head.i] = true;
            cost += head.cost;

            if (head.cost > 0) {
                output.append(head.from + 1).append(" ").append(head.i + 1).append("\n");
                newBridges++;
            }
            checked++;
            if(checked==N) {
                return;
            }
            for (int c = 0; c < N; c++) {
                if (graph[head.i][c] > 0 && !visited[c]) {
                    pq.offer(new Vertex(c, graph[head.i][c], head.i));
                }
            }
        }
    }

    static class Vertex implements Comparable<Vertex> {
        // idx, from, cost
        int i, cost, from;

        public Vertex(int i, int cost, int from) {
            super();
            this.i = i;
            this.cost = cost;
            this.from = from;
        }
        @Override
        public int compareTo(Vertex o) {
            return Integer.compare(this.cost, o.cost);
        }
    }
}

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

문제

문제

출처

ICPC

어떤 조건을 빼먹은걸까요?

gray22 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말