도시 분할 계획

☑️ 1. 문제 설명

N개의 마을과 그 마을을 연결하는 M개의 길이 있다. 이 마을을 두 개로 분리하여 관리하고 싶다. 최소의 길만 존재하게 하면서 길의 유지비가 최소가 되도록 하여라. 분리된 두 마을 사이에는 길이 없다.

☑️ 2. 알고리즘 선정

이 문제는 결국 마을의 모든 집을 연결하면서 총 유지비를 최소로 만드는 문제이므로, 최소 신장 트리를 만드는 과정과 같다. 이 MST를 두 개의 마을로 나누기 위해서는, MST를 이루는 간선 중 가장 비싼 간선 하나를 제거하면 된다.

프림 알고리즘으로 MST를 만들 수 있다.

프림 알고리즘란?

프림 알고리즘은 하나의 정점에서 연결된 간선들 중에서 하나씩 선택하면서 MST를 만들어가는 방식이다.

1. 임의 정점을 선택하여 시작하고
2. 선택한 정점과 인접하는 정점들 중에 최소 비용의 간선을 가진 정점을 선택한다.
3. 모든 정점이 선택될 때까지 2의 과정을 반복한다.

☑️ 3. 풀이 절차

그래프 정보 입력받기

1. 마을의 집(정점) 개수 N과 길(간선)의 개수 M을 입력받는다.

2. 간선 정보를 관리하기 위해 Edge 클래스를 만들고, 간선의 도착지 to와 유지비(가중치) path를 담는다.

3. PriorityQueue가 비용이 가장 낮은 간선을 자동으로 선택하도록, Edge 클래스에 Comparable 인터페이스를 구현한다.

4. 각 집과 연결된 길들을 저장하기 위해 인접 리스트인 List<Edge>[] home을 초기화한다.

5. M개의 간선 정보를 입력받아 home 리스트에 양방향으로 추가한다.

프림(Prim) 알고리즘으로 MST를 구축

프림 알고리즘은 우선순위 큐(PriorityQueue)와 방문 배열을 사용해 비용이 가장 낮은 간선부터 하나씩 추가하며 MST를 만들어 나가는 방식이다.

1. boolean[] visited 배열을 만들어 방문한 집을 체크한다.

2. PriorityQueue<Edge> pq를 생성한다. 이 큐는 항상 비용이 가장 적은 간선을 우선으로 꺼내준다.

3. 임의의 시작점(예: 1번 집)을 정해 visited 배열을 true로 바꾸고, 이 집과 연결된 모든 간선을 pq에 넣는다.

4. 반복문: MST를 완성하기 위해 N-1개의 간선을 선택할 때까지 다음 과정을 반복한다.

   1) pq에서 가장 비용이 적은 간선 e를 꺼낸다.

   2) e의 도착지 e.to가 이미 방문한 집이라면, 이미 더 저렴한 경로가 있다는 뜻이므로 이 간선을 버리고 다음 간선을 꺼낸다.

   3) 아직 방문하지 않은 집이라면, 이 간선을 최소 신장 트리의 일부로 선택한다.

   4) e.to를 visited 처리하고, 선택한 간선의 비용(e.path)을 costs 리스트에 저장한다.

   5) 마지막으로, 새로 방문한 e.to와 연결된 모든 간선들을 pq에 추가하여 다음 단계에서 탐색할 후보에 포함시킨다.

마을을 두 개로 나누기

1. 위 단계에서 costs 리스트에 MST를 구성하는 N-1개의 간선 비용이 모두 저장된다.

2. 마을을 두 개로 나누기 위해, MST를 이루는 간선들 중 가장 비용이 큰 간선 하나를 제거한다. 이 간선을 제거하면 그래프는 자연스럽게 두 개의 연결 요소(마을)로 나뉘게 된다.

3. Collections.max(costs)를 사용해 costs 리스트에서 가장 큰 값을 찾는다.

4. costs 리스트의 모든 비용을 더한 총합에서 가장 큰 비용을 빼면, 최종적으로 두 마을을 유지하는 데 드는 최소 비용을 얻을 수 있다.

☑️4. 코드 구현

package study;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class 도시분할계획_1647 {

	// 우선순위 큐로 만들기
	static class Edge implements Comparable<Edge> { // Comparable 넣는 걸 까먹었다.
		int to;
		int path;

		public Edge(int to, int path) {
			super();
			this.to = to;
			this.path = path;
		}

		@Override
		public int compareTo(Edge o) {
			return this.path - o.path;
		}
	}

	public static void main(String[] args) throws IOException {
		System.setIn(new FileInputStream("src/input.txt"));

		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<Edge>[] home = new ArrayList[N + 1];
		for (int i = 1; i <= N; i++) {
			home[i] = 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());

			home[A].add(new Edge(B, C));
			home[B].add(new Edge(A, C));
		}

		// 최소신장트리 만들기
		PriorityQueue<Edge> pq = new PriorityQueue<>();
		boolean[] visited = new boolean[N + 1];
		visited[1] = true;
        
		int pick = 0; 
		List<Integer> costs = new ArrayList<>();

		for (Edge e : home[1]) { 
			pq.add(e);
		}

		// N -1개 뽑을 때까지 반복
		while (pick < N - 1) {
			Edge e = pq.poll(); // 비용이 가장 적은 간선을 꺼낸다.
			// 이미 방문했으면 넘어가
			if (visited[e.to]) {
				continue;
			}
			visited[e.to] = true;
			pick++;
			costs.add(e.path);

			pq.addAll(home[e.to]);'`
		}

		int maxCost = Collections.max(costs);
		int totalCost = 0;

		for (int i = 0; i < costs.size(); i++) {
			totalCost += costs.get(i);
		}
		int ans = totalCost - maxCost;

		System.out.println(ans);

	}
}