이번에 풀어본 문제는
백준 1647번 도시 분할 계획 입니다.

📕 문제 링크

❗️코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Load {
    int end;
    int weight;

    public Load(int end, int weight) {
        this.end = end;
        this.weight = weight;
    }
}
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());

        List<List<Load>> map = new ArrayList<>();
        for (int i = 0; i <= N; i++) map.add(new ArrayList<>());

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            int C = Integer.parseInt(st.nextToken());

            map.get(A).add(new Load(B, C));
            map.get(B).add(new Load(A, C));
        }

        boolean [] isVisited = new boolean[N + 1];
        // 시작은 1
        Queue<Integer> resultQ = new PriorityQueue<>(Collections.reverseOrder());

        Queue<Load> q = new PriorityQueue<>((o1, o2) -> o1.weight - o2.weight);
        q.add(new Load(1, 0));

        //Prim
        while (!q.isEmpty()) {
            Load cur = q.poll();

            if (isVisited[cur.end]) continue;
            isVisited[cur.end] = true;
            resultQ.add(cur.weight);

            for (Load next : map.get(cur.end)) {
                if (!isVisited[next.end]) q.add(next);
            }
        }

        // 가장 큰 간선 제거 (마을 분리)
        resultQ.poll();

        int answer = 0;
        while (!resultQ.isEmpty()) answer += resultQ.poll();

        System.out.print(answer);
    }
}

📝 풀이

마을에 불필요한 도로를 제거하고, 관리를 분할하기 위해 마을을 두 덩어리로 분리하는 문제입니다.
가중치가 최소인 경로를 남겨야 하므로 MST(최소 스패닝트리)를 구하고, 마을을 분리하면서 가중치를 최소로 유지하기 위해 MST에서 가장 가중치가 큰 경로 하나를 제거해주면 해결할 수 있습니다.
MST는 Prim 알고리즘을 사용하여 구현했습니다.