문제 설명
백준 1647번. 도시 분할 계획
https://www.acmicpc.net/problem/1647
동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그러다가 평화로운 마을에 가게 되었는데, 그곳에서는 알 수 없는 일이 벌어지고 있었다.
마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 각 길마다 길을 유지하는데 드는 유지비가 있다. 임의의 두 집 사이에 경로가 항상 존재한다.
마을의 이장은 마을을 두 개의 분리된 마을로 분할할 계획을 가지고 있다. 마을이 너무 커서 혼자서는 관리할 수 없기 때문이다. 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야 한다. 각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 한다는 뜻이다. 마을에는 집이 하나 이상 있어야 한다.
그렇게 마을의 이장은 계획을 세우다가 마을 안에 길이 너무 많다는 생각을 하게 되었다. 일단 분리된 두 마을 사이에 있는 길들은 필요가 없으므로 없앨 수 있다. 그리고 각 분리된 마을 안에서도 임의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 더 없앨 수 있다. 마을의 이장은 위 조건을 만족하도록 길들을 모두 없애고 나머지 길의 유지비의 합을 최소로 하고 싶다. 이것을 구하는 프로그램을 작성하시오.
문제 간략화
N개의 집의 개수(정점의 개수), M개의 길이의 개수(간선의 개수)를 입력 ㅂ다는다.
각각의 간선 별로 유지비용 입력 받는다.
최종적으로는길을 하나 더 없애면서 마을을 분리하고 유지비의 합을 최소로 만드는 방법을 구해야한다.
-> 모두를 잇는 최소의 길이인 최소 신장(스패닝)을 구하고, 가장 유지비용이 큰 간선에 대하여 없애자!
설계 스크래치 (풀이 절차)
- 간선에 대한 정보를 입력 받는 Edge 클래스를 준비 (Edge to, from, cost 입력 받음)
- 최소 신장에 대하여 우선적으로 계산을 해야함 -> 크루스칼 알고리즘 채택
- Disjoint Set(DSU)의 find/union을 사용해서 사이클이 생기지 않는 길만 고른다.
- 이렇게 뽑힌 길들의 합이 최소 신장 트리(= MST)가 됨!
- 모든 정점들을 잇는 최소 신장에 간선 중에서, 가장 비용이 큰 간선을 제거해주면 마을을 분리하고, 최소의 비용을 지불하는 것이 가능
=> 즉, 싼 길부터 골라서 MST를 만든 뒤에, 그 중에서 제일 비싼 길을 하나 빼주면 "두 마을 + 최소 비용" 을 동시에 만족하는 게 가능함
설계 코드
- 전역 변수
간선에 대한 정보를 저장하는 Edge 클래스를 생성
static class Edge {
int from;
int to;
int cost;
Edge(int from, int to, int cost) {
this.from = from;
this.to = to;
this.cost = cost;
}서로소 집합에 대하여 저장하는 Disjoint Set Union 기반의 클래스 생성(DSU)
static class Disjoint {
int[] parent;
int[] rank;
Disjoint(int n) {
parent = new int[n + 1]; // 1-based
rank = new int[n +1];
for (int i = 1; i <= n; i++) {
parent[i] = i;
rank[i] = 0;
}
}
// 생략DSU의 내부 메서드 : find(int x) 와 union(int x, int y)
-> 부모를 찾는 find 메서드와 더 큰 부모를 기반으로 합치는 union 메서드를 클래스 메서드로 구현해줌
어떤 정점이 어느 그룹(부모)에 속해있는지를 저장
- find 메서드 : 부모(= 그룹의 대표)를 찾는 역할
계속 부모를 따라가면 결국 하나의 대표 점(루트)에 도착을 한다.
// find ( root)
int find(int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
} - union 메서드 : 서로 다른 두 그룹을 하나로 합쳐주는 메서드로 설계, 서로 연결되어있지 않은 그룹의 경우 합쳐준다고 생각하면 됨
boolean으로 타입을 설정함으로써 순회(같은 그룹)이면 false를 반환하고(더이상 합칠 필요가 없으니까),
그리고 같은 그룹이 아니라면 true를 반환하면서 최소 비용의 간선 대상에 추가를 해준다.
그룹을 합칠 대에는 트리의 높이(rank)를 기준으로 더 높은 쪽을 부모로 삼는다.
이러면 트리가 덜 깊어져서 find가 빨라질 수 있음
// union
boolean union(int a, int b) {
int rootA = find(a);
int rootB = find(b);
if (rootA == rootB) {
return false;
}
// rank가 큰 쪽을 부모로 설정
if (rank[rootA] < rank[rootB]) {
parent[rootA] = rootB;
}
else if (rank[rootA] > rank[rootB]) {
parent[rootB] = rootA;
}
else {
parent[rootB] = rootA;
rank[rootA]++;
}
return true;
}사실 여기서의 rank는 union을 위한 계산을 위해 설정해둔 것이지,
실제의 rank와 일치할 필요는 없다.(실제 트리 깊이와 정확히 일치하지는 않을 수 있음)
total: 최소 비용의 합을 합침.
사이클(돌아오는 길)을 만들지 않는 선에서 최소 비용만 골라서 더한다. (= union에서 true인 애들만 더한다)
길을 하나 고를때마다 union을 이용해서 두 점을 합쳐주고,
그 비용을 total에 합친다.
정점이 N개라면 사실 최소의 연결을 위해서는 N-1개만 필요하니까,
이미 N-1개의 길을 골랐다면 종료해주는 조건도 추가
for (Edge edge : edgeList) {
if (d.union(edge.from, edge.to)) {
total += edge.cost;
if (maxMSTCost < edge.cost) {
maxMSTCost = edge.cost;
}
if (++used == N -1) {
break;
}
}그리고 문제에서 요구했듯이,
마을을 분리함으로써 최소 비용을 사용하고 싶다했으므로,
먼저 전체를 최소 비용으로 연결한 MST를 만든 뒤에
그 MST에 들어간 간선들(길, Edge) 중에서 "가장 비싼 간선" 하나를 골라서 빼준다!
maxMSTCost: MST를 만들면서 가장 비싼 간선 비용
최종 답을 구할 때에는 total -maxMSTCost로 계산해서 간선을 제외해줌
코드 구현
import java.io.*;
import java.util.*;
public class P1647_도시분할계획 {
static class Edge {
int from;
int to;
int cost;
Edge(int from, int to, int cost) {
this.from = from;
this.to = to;
this.cost = cost;
}
}
static class Disjoint {
int[] parent;
int[] rank;
Disjoint(int n) {
parent = new int[n + 1]; // 1-based
rank = new int[n +1];
for (int i = 1; i <= n; i++) {
parent[i] = i;
rank[i] = 0;
}
}
// find ( root)
int find(int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
// union
boolean union(int a, int b) {
int rootA = find(a);
int rootB = find(b);
if (rootA == rootB) {
return false;
}
// rank가 큰 쪽을 부모로 설정
if (rank[rootA] < rank[rootB]) {
parent[rootA] = rootB;
}
else if (rank[rootA] > rank[rootB]) {
parent[rootB] = rootA;
}
else {
parent[rootB] = rootA;
rank[rootA]++;
}
return true;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st1 = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st1.nextToken());
int M = Integer.parseInt(st1.nextToken());
Edge[] edgeList = new Edge[M];
// 입력받기
for (int i = 0; i < M; i++) {
StringTokenizer st2 = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st2.nextToken());
int b = Integer.parseInt(st2.nextToken());
int c = Integer.parseInt(st2.nextToken());
Edge tempEdge = new Edge(a, b, c);
edgeList[i] = tempEdge;
}
// 비용에 대한 정렬
Arrays.sort(edgeList, Comparator.comparingInt(e -> e.cost));
// 서로소 집합끼리의 가중치 구하기
Disjoint d = new Disjoint(N);
long total = 0;
int used = 0;
int maxMSTCost = 0;
for (Edge edge : edgeList) {
if (d.union(edge.from, edge.to)) {
total += edge.cost;
if (maxMSTCost < edge.cost) {
maxMSTCost = edge.cost;
}
if (++used == N -1) {
break;
}
}
}
System.out.println(total-maxMSTCost);
}
}