문제
https://www.acmicpc.net/problem/21924
풀이
- 신도시에 건물 사이를 잇는 양방향 도로를 만들려는 공사 계획을 세웠다.
- 공사하는 데 드는 비용을 아끼려고 한다.
- 모든 건물이 도로를 통해 연결되도록 최소한의 도로를 만드려고 한다.
- 전체 도로를 생성하는 것에 대비해 최소 비용으로 도로를 만들면, 얼마나 절약되는지 출력하자.
최소 신장 트리(MST)를 구하는 문제입니다.
주어지는 모든 건물과 건물 사이의 도로를 잇는 가중치를 이용해 최소 비용만 사용하여 도로를 만들면 됩니다.
여기서 도로는 (노드 - 1)개를 건설하면 최소 비용으로 모두 연결된 상태를 구할 수 있습니다.
입력
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
make();
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());
edges.add(new Edge(a, b, c));
total += c;
}n: 건물의 개수m: 도로의 개수make: 유니온 파인드를 위한 부모, 사이즈 배열 초기화 및 도로의 정보를 담은 배열(edges) 초기화, 총 간선의 비용 초기화
Edge 클래스
static class Edge implements Comparable<Edge> {
int u, v, w;
public Edge (int u, int v, int w) {
this.u = u;
this.v = v;
this.w = w;
}
@Override
public int compareTo(Edge o) {
return Integer.compare(this.w, o.w);
}
}u: 시작 지점v: 도착 지점w: 가중치- 가중치를 오름차순으로 정렬해 주도록,
compareTo오버라이딩
make()
private static void make() {
edges = new ArrayList<>();
total = 0;
p = new int[n+1];
s = new int[n+1];
for (int i = 1; i <= n; i++) {
p[i] = i;
s[i] = 1;
}
}edges: 간선의 정보를 담은 배열total: 모든 간선의 가중치p: 각 노드의 부모 배열(자기 자신으로 초기화)s: 각 노드의 크기 배열(자신 혼자 있으니 1로 초기화)
MST
cost = kruskal();- 최소 신장 트리를 구해보겠습니다.
find
private static int find(int x) {
if (p[x] == x) return x;
return p[x] = find(p[x]);
}- 만약 자신의 부모가 자기 자신일 때는, 자기 자신 리턴
- 아닐 경우 경로 압축을 통해 부모의 부모 리턴
union
private static boolean union(int a, int b) {
int ra = find(a), rb = find(b); // 각 노드의 부모
if (ra == rb) return false; // 부모가 같을 경우 false
// rb가 더 클 경우 swap
if (s[ra] < s[rb]) {
int t = ra;
ra = rb;
rb = t;
}
// rb의 부모를 ra로 설정
p[rb] = ra;
s[ra] += s[rb];
return true;
}- 부모가 같을 경우 union 연산이 이루어지지 않았으므로,
false를 리턴해 줍니다. ra가rb이상일 경우에rb를ra의 밑으로 넣을 것이기 때문에,rb가 더 클 경우에는 서로 자리를 바꿔서 연산해 줍니다.
Kruskal
private static long kruskal() {
Collections.sort(edges);
long mstCost = 0;
int usedEdges = 0;
for (Edge e : edges) {
if (union(e.u, e.v)) {
mstCost += e.w;
if (++usedEdges == n - 1) return mstCost;
}
}
return -1;
}- 간선을 연결해주기 전, 가중치 기준으로 정렬해 줍니다.
union연산이 이루어지면(return true), 도로를 이어준 것이므로 간선 가중치를 더해줍니다.- 만약 간선이 (노드 - 1)개로 이루어졌다면, 모든 노드가 연결되었다는 뜻이므로 메서드를 종료합니다.
- 반복문이 다 돌았는데도 리턴하지 못했다는 것은, 모든 노드를 연결하는 간선이 생성되지 않았다는 것이므로
-1을 리턴하였습니다.
출력
System.out.println(cost == -1 ? -1 : total - cost);- 절약한 비용을 출력해야 하므로, (전체 도로 건설 비용 - 최소 비용)을 출력합니다.
- 만약 도로를 짓지 못했다면,
-1을 출력
코드
import java.util.*;
import java.io.*;
public class Main {
static class Edge implements Comparable<Edge> {
int u, v, w;
public Edge (int u, int v, int w) {
this.u = u;
this.v = v;
this.w = w;
}
@Override
public int compareTo(Edge o) {
return Integer.compare(this.w, o.w);
}
}
static int n, m;
static long total, cost;
static int[] p, s;
static List<Edge> edges;
private static void make() {
edges = new ArrayList<>();
total = 0;
p = new int[n+1];
s = new int[n+1];
for (int i = 1; i <= n; i++) {
p[i] = i;
s[i] = 1;
}
}
private static int find(int x) {
if (p[x] == x) return x;
return p[x] = find(p[x]);
}
private static boolean union(int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) return false;
if (s[ra] < s[rb]) {
int t = ra;
ra = rb;
rb = t;
}
p[rb] = ra;
s[ra] += s[rb];
return true;
}
private static long kruskal() {
Collections.sort(edges);
long mstCost = 0;
int usedEdges = 0;
for (Edge e : edges) {
if (union(e.u, e.v)) {
mstCost += e.w;
if (++usedEdges == n - 1) return mstCost;
}
}
return -1;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
make();
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());
edges.add(new Edge(a, b, c));
total += c;
}
cost = kruskal();
System.out.println(cost == -1 ? -1 : total - cost);
}
}