문제

BOJ 1647: 도시 분할 계획 https://www.acmicpc.net/problem/1647

풀이

조건

• 길의 유지비의 합을 최소로 한다.
  • 최소 스패닝 트리를 구한다.
• 마을을 두 개의 분리된 마을로 분할한다.
• 답이 int형의 범위를 벗어날 수 있으므로 long타입으로 선언해 구한다.

풀이 순서

• 크루스칼 알고리즘을 사용한다.
• 유지비를 기준으로 오름차순으로 정렬한다.
• Union&Find를 사용해 트리에 사이클이 있는지 확인한다.
• 모두 연결된 상태에서 유지비가 가장 큰 도로만 제거하면 마을이 2개로 갈라지게 된다.
  • 연결 다리 중 최대 비용을 미리 구해놨다가 결과에서 빼주면 된다.

코드

Java

package project1;

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

public class Main {
	
	static int N, M;
	static int[] parent; // 집합 기록할 배열
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		long answer = 0;
		
		st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		Edge[] edges = new Edge[M];
		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());
			// 더 작은 마을 번호가 앞으로 가게 저장 
			if(a <= b) {
				edges[i] = new Edge(a, b, c);
			} else {
				edges[i] = new Edge(b, a, c);
			}
			
		}
		
		// 유지비를 기준으로 오름차순 정렬
		Arrays.sort(edges, new Comparator<Edge>() {
			@Override
			public int compare(Edge o1, Edge o2) {
				return Integer.compare(o1.cost, o2.cost);
			}
		});
		
		// 집합 저장할 배열 초기화
		parent = new int[N + 1];
		for(int i = 1; i <= N; i++) {
			parent[i] = i;
		}
		
		int target = 0; // 연결한 길 중 가장 큰 값 구하기 -> 나중에 이 길을 제거하면 마을이 2개로 갈라짐
		// 크루스칼 시작
		for(int i = 0; i < M; i++) {
			Edge edge = edges[i];
			
			// 사이클이 없다면
			if(!isSameParent(edge.s, edge.e)) {
				// 합치기
				union(edge.s, edge.e);
				
				// 유지비 누적
				target = Math.max(target, edge.cost); // 연결한 길 중 가장 큰 값 구하기
				answer += edge.cost;
			}
		}
		
		// 연결된 모든 길 중 유지비가 가장 큰 길은 제거 -> 마을 2개로 갈라지는 효과
		System.out.println(answer - target);
	}
	
	// 하나의 집합으로 합치기
	static void union(int x, int y) {
		x = find(x);
		y = find(y);
		
		// 마을 번호가 더 작은 집합으로 합침
		if(x < y) {
			parent[y] = x;
		} else {
			parent[x] = y;
		}
	}
	
	// 어느 집합에 속해있는지 확인
	static int find(int x) {
		if(parent[x] == x) {
			return x;
		}
		
		return parent[x] = find(parent[x]);
	}
	
	// 같은 집합에 속해 있는지 확인 -> 사이클인지 확인함
	static boolean isSameParent(int x, int y) {
		x = find(x);
		y = find(y);
		
		if(x == y) {
			return true;
		}
		
		return false;
	}
	
	static class Edge {
		int s, e, cost;
		
		public Edge(int s, int e, int cost) {
			this.s = s;
			this.e = e;
			this.cost = cost;
		}
	}
}

정리

• 크루스칼 알고리즘의 풀이를 살짝 응용하는 문제여서 재밌었다.