[백준/JAVA] 1647_도시 분할 계획

백준🔗

1647번: 도시 분할 계획

 

문제

 

 

간단 풀이

이 문제는 최소 스패닝 트리 알고리즘을 사용하되, 마을을 2개로 분할해야 하기 때문에 최소 스패닝 트리를 만들었을 때 연결된 길 중에서 가장 유지비가 큰 길을 하나 빼서 답을 구했다.

 

어제 풀었던 문제에서 크루스칼, 프림 알고리즘을 정리했는데, 이번 문제에서는 프림 알고리즘을 적용해서 풀었다.

 

👇최소 스패닝 트리 관련 알고리즘(크루스칼, 프림) 정리 보러가기

2023.06.16 - [알고리즘/백준] - [백준/JAVA] 1197_최소 스패닝 트리

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws Exception {
		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>[] graph = new ArrayList[N + 1];
		for (int i = 1; i <= N; i++) {
			graph[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());
			// 양방향
			graph[A].add(new Edge(B, C));
			graph[B].add(new Edge(A, C));
		}

		boolean[] visited = new boolean[N + 1];
		PriorityQueue<Edge> pq = new PriorityQueue<>();
		// 시작 정점
		int W = 0;
		int max = 0;
		int pick = 1;
		visited[1] = true;
		for (Edge e : graph[1]) {
			pq.add(e);
		}
		while (pick != N) {
			Edge cur = pq.poll();
			if (visited[cur.ed]) {
				continue;
			}
			visited[cur.ed] = true;
			W += cur.w;
			max = (max < cur.w) ? cur.w : max;
			pick++;
			for (Edge e : graph[cur.ed]) {
				if (!visited[e.ed]) {
					pq.add(e);
				}
			}
		}
		System.out.println(W - max);
	}

	static class Edge implements Comparable<Edge> {
		int ed, w;

		public Edge(int ed, int w) {
			this.ed = ed;
			this.w = w;
		}

		@Override
		public int compareTo(Edge o) {
			return Integer.compare(this.w, o.w); // 가중치 오름차순
		}
	}
}

 

참고 자료