https://www.acmicpc.net/problem/1647
이번 문제는 간단한 MST문제로 모든 집들을 연결하는 최소 신장트리를 생성한 후 연결된 edge들 중에서 길이가 가장 긴 edge를 잘라 두개의 마을을 만들면 되는 문제이다.
저는 문제 풀이를 Kruskal's algorithm으로 풀이하였으며 코드는 아래와 같습니다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
public class Main {
static int N; // 집의 개수
static int M; // 길의 개수
static ArrayList<Edge> edgeList = new ArrayList<>();
static int[] parent;
static int result = 0;
static int lastConnect; // 마지막으로 연결된 길의 weight저장
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
parent = new int[N+1];
for (int i=1; i<=N; i++) parent[i] = i;
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());
edgeList.add(new Edge(A, B, C));
}
Collections.sort(edgeList);
kruskal();
result -= lastConnect;
System.out.println(result);
}
static void kruskal() {
for (Edge e: edgeList) {
union(e);
}
}
static int find(int nodeId) {
if (parent[nodeId] == nodeId) return nodeId;
else return parent[nodeId] = find(parent[nodeId]);
}
static void union(Edge e) {
int node1 = find(e.node1);
int node2 = find(e.node2);
if (node1 != node2) {
result += e.weight;
lastConnect = e.weight;
parent[node1] = node2;
}
}
static class Edge implements Comparable<Edge> {
int node1;
int node2;
int weight;
public Edge(int node1, int node2, int weight) {
this.node1 = node1;
this.node2 = node2;
this.weight = weight;
}
@Override
public int compareTo(Edge o) {
return this.weight-o.weight;
}
}
}
🚨compareTo 주의할 점
이전까지 comapareTo를 override할 때는 아래의 코드와 같이 작성하였다. 하지만 이러한 경우 두개의 값이 같아서 0을 return하는 경우가 없게 되어 위의 문제를 풀 때 런타임 에러가 발생하였었다.@Override public int compareTo(Edge o) { return this.weight < o.weight ? -1:1; }
그래서 다음부터 compareTo를 재정의 할 때는 아래와 같이 해당 값들을 뺀 값을 return하도록 해주자~!!!
@Override public int compareTo(Edge o) { return this.weight-o.weight; }