[백준] 1647 - 도시 분할 계획

[문제링크]

1647번: 도시 분할 계획

 

0. 집 사이의 연결을 유지하며 길을 제거하고, 최소 비용의 길들을 사용해 전체를 연결하기 == 최소 신장 트리(MST)

 

1. 최소 신장 트리를 구하면 최소 거리의 길들로 모든 마을을 연결할 수 있다

 

2. 완성된 MST의 간선들 중 하나를 제거하면 2개의 tree가 생성된다

  - 마을을 2개로 분리할 수 있다

 

3. 길의 유지비의 합은 항상 최소를 유지해야하므로, MST를 이루는 간선들 중 가중치가 가장 큰 간선 하나를 제거하면 마을을 분리하면서 비용을 최소로 만들 수 있다

  - Kruskal의 경우, 간선을 기준으로 최소 간선부터 고려하므로, 마지막에 선택할 간선을 선택하지 않아도 된다

  - N개의 집이 있을때, N-1개가 아닌 N-2개만 선택하는 것

 

<Kruskal 사용>

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
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 = pint(st.nextToken());
		int m = pint(st.nextToken());

		//간선 리스트..대신 크기가 주어지니 배열 사용
		edge[] e = new edge[m];
		for (int i = 0; i < m; i++) {
			e[i]=new edge();
			st = new StringTokenizer(br.readLine(), " ");
			
			e[i].n1=pint(st.nextToken());
			e[i].n2=pint(st.nextToken());
			e[i].cost=pint(st.nextToken());
		}
		
		Arrays.sort(e);
		
		init(n);
		
		int cnt=0, i=0;//현재 선택한 edge의 갯수
		int totalCost=0;//누적 전체cost
		while(true) {
			//union이 정상적으로 수행 됬다면
			if(union(e[i].n1, e[i].n2)) {
				//cnt, cost 반영
				cnt++;
				totalCost+=e[i].cost;
			}
			if(cnt==n-1)break;
			i++;
		}
		//최소 cost의 2개의 마을로 분할하는 법 = MST에서 가장 cost가 큰 edge 하나 자르기
		System.out.println(totalCost-e[i].cost);
	}

	//분리집합
	static int[]parents;
	static void init(int n) {
		parents=new int[n+1];
		for (int i = 0; i <= n; i++) {
			parents[i]=i;
		}
	}
	static int find(int n) {
		if(parents[n]==n)return n;
		return parents[n]=find(parents[n]);
	}
	static boolean union(int n1, int n2) {
		int p1=find(n1);
		int p2=find(n2);
		
		if(p1==p2)return false;
		parents[p1]=p2;
		return true;
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
	//간선 객체
	static class edge implements Comparable<edge>{
		int n1;
		int n2;
		int cost;
		@Override
		public int compareTo(edge e) {
			return this.cost-e.cost;
		}		
	}
}

<Prim 사용>

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
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 = pint(st.nextToken());
		int m = pint(st.nextToken());

		ArrayList<ArrayList<int[]>>graph = new ArrayList<>();
		for (int i = 0; i <= n; i++) {
			graph.add(new ArrayList<>());
		}
		//그래프 입력
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int x = pint(st.nextToken());
			int y = pint(st.nextToken());
			int cost = pint(st.nextToken());

			graph.get(x).add(new int[] {y,cost});
			graph.get(y).add(new int[] {x,cost});
		}
		
		int totalCost=0, cnt=0, max=-1;
		//전처리
		boolean[] isV = new boolean[n+1];
		PriorityQueue<int[]>pq = new PriorityQueue<>(new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				// TODO Auto-generated method stub
				return o1[1]-o2[1];
			}
		});
		for (int i = 1; i <= n; i++) {
			pq.offer(new int[] {i,Integer.MAX_VALUE});
		}
		//임의의 시작 노드 설정
		pq.offer(new int[] {1,0});
		
		while(cnt!=n) {
			int[] curNode = pq.poll();

			if(isV[curNode[0]])continue;//이미 방문한 node면
			
			isV[curNode[0]]=true;
			totalCost+=curNode[1];
			if(max<curNode[1])max=curNode[1];
			cnt++;
			
			for (int i = 0; i < graph.get(curNode[0]).size(); i++) {
				int[] next = graph.get(curNode[0]).get(i);
				if(!isV[next[0]]) {
					pq.offer(next);
				}
			}
			
		}
		System.out.println(totalCost-max);
		
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면(1,2 - Kruskal, 3 - Prim)