백준 1647 도시 분할 계획 Java [최소스패닝트리, 프림]

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

1647번: 도시 분할 계획

 

 

최소 신장 트리(MST) 문제이다

문제 조건에서 2개의 마을로 분리한다고 했기 때문에

전체 가중치를 구하고 가중치 중에서 가장 큰 값을 빼주면 된다

 

import java.io.*;
import java.util.*;

public class Main {
    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());
        ArrayList<int[]>[] routes = new ArrayList[N+1];
        for (int n = 0; n <= N; n++) {
            routes[n] = new ArrayList<>();
        }
        for (int m = 0; m < M; m++) {
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            int C = Integer.parseInt(st.nextToken());
            routes[A].add(new int[]{B, C});
            routes[B].add(new int[]{A, C});
        }
        boolean[] vtd = new boolean[N + 1];
        int count = N;
        int cost = 0;
        int max_cost = 0;
        PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o[1]));
        queue.add(new int[]{1, 0});
        while (count > 0 && !queue.isEmpty()) {
            int[] now = queue.poll();
            if (vtd[now[0]]) continue;
            vtd[now[0]] = true;
            cost += now[1];
            max_cost = Math.max(now[1], max_cost);
            count--;
            for (int[] route : routes[now[0]]) {
                if (!vtd[route[0]]) queue.add(route);
            }
        }
        System.out.println(cost-max_cost);
    }
}

 

프림알고리즘이 느리기 때문에 시간을 줄여보려고 정점 1개만 방문하지 않게 로직을 짜서 많이 틀렸다

처음엔 시작점을 1로 고정해놓고 1개만 방문하지 않게 로직을 짰다

시작점을 방문하지 않을 경우를 고려하지 않아서 틀린줄알고

간선 중 가중치 최소값을 시작점으로 잡고 했는데도 틀렸다

결국엔 정석적으로 모두 구해서 최대값을 빼버렸다