https://www.acmicpc.net/problem/1922
문제 요약
각 컴퓨터를 연결하는데 필요한 비용이 주어졌을 때 모든 컴퓨터를 연결하는데 필요한 최소비용을 얻어라.
컴퓨터의 수 N은 최대 1000이다.
주어지는 연결의 수는 최대 10만이다.
문제 접근
이 문제는 그래프가 주어지고, 최소 비용으로 모든 컴퓨터가 하나의 그래프에 그대로 모두 연결되는 것을 구하는 것이기 때문에 최소 신장 트리를 얻는 것과 같다는 것을 알 수 있다.
최소 신장 트리를 얻는 알고리즘은 크게 크루스칼 알고리즘과 프림 알고리즘이 있다.
크루스칼 알고리즘은 다음과 같이 작동한다.
- 모든 연결을 비용의 오름차순으로 정렬하고, 하나씩 연결한다.
- 다만 이미 연결된 경우에는 연결할 필요가 없다.
- 이를 위해 유니온 파인드를 사용한다.
- 모두 연결한 뒤, 사용한 최소 비용을 출력한다.
크루스칼 알고리즘은 유니온 파인드를 사용해야 하는데, 이는 그래프의 두 노드가 연결되었는지 확인하는 것이다.
프림 알고리즘은 다음과 같이 작동한다.
- 특정 노드 하나를 시작점으로 잡고, 해당 노드의 연결을 비용의 오름차순으로 정렬하고, 하나를 연결한다.
- 다만 이미 연결된 경우에는 연결할 필요가 없다.
- 이를 위해 방문 여부 배열을 사용한다.
- 새로 연결된 노드의 연결까지 포함하여 다시 비용의 오름차순으로 정렬한 뒤 다음 연결을 수행한다.
- 모두 연결한 뒤, 사용한 최소 비용을 출력한다.
풀이
크루스칼 알고리즘
기본적인 아이디어는 다음과 같다.
- (추가 예정)
이를 구현한 코드는 다음과 같다.
import java.util.*;
import java.io.*;
public class Main {
static int[] parent;
// 해당 노드의 루트 노드 찾기
public static int find(int a) {
if (parent[a] == a) return a;
return parent[a] = find(parent[a]);
}
// 두 노드를 같은 트리로 연결하기
// a의 루트 노드의 루트를 b의 루트 노드로 설정
public static void union(int a, int b) {
int aRoot = find(a);
int bRoot = find(b);
parent[aRoot] = bRoot;
}
public static void main(String[] args) throws IOException {
// 입력 받기
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine()); // 노드 개수
int M = Integer.parseInt(br.readLine()); // 엣지 개수
int[][] edges = new int[M][3];
// 엣지에는 방향이 없다.
for (int i = 0; i < M; i++) {
StringTokenizer stM = new StringTokenizer(br.readLine());
edges[i][0] = Integer.parseInt(stM.nextToken()); // 노드 a
edges[i][1] = Integer.parseInt(stM.nextToken()); // 노드 b
edges[i][2] = Integer.parseInt(stM.nextToken()); // 비용
}
// 연결 선을 비용의 오름차순으로 정렬한다.
Arrays.sort(edges, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return Integer.compare(o1[2], o2[2]);
}
});
// 연결 선을 순서대로 보며 최소 신장 트리를 구성한다.
// 두 노드의 루트가 같다면 연결하지 않고, 다르다면 연결한다.
// 연결한 선의 비용을 누적해서 기록한다.
parent = new int[N+1]; // 해당 인덱스 노드의 부모 노드 번호를 나타내는 배열
for (int i = 0; i < N+1; i++) {
parent[i] = i;
}
int totalCost = 0; // 사용한 비용 기록
for (int i = 0; i < M; i++) {
int a = edges[i][0]; // 노드 a
int b = edges[i][1]; // 노드 b
int c = edges[i][2]; // 비용
if (find(a) == find(b)) continue;
union(a, b);
totalCost += c;
}
// 정답 출력
System.out.println(totalCost);
}
}프림 알고리즘
기본적인 아이디어는 다음과 같다.
- (추가 예정)
이를 구현한 코드는 다음과 같다.
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
// 입력 받기
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine()); // 노드 개수
int M = Integer.parseInt(br.readLine()); // 엣지 개수
ArrayList<int[]>[] graph = new ArrayList[N+1];
for (int i = 0; i < N+1; i++) {
graph[i] = new ArrayList<>();
}
// 엣지에는 방향이 없다.
for (int i = 0; i < M; i++) {
StringTokenizer stM = new StringTokenizer(br.readLine());
int a = Integer.parseInt(stM.nextToken()); // 노드 a
int b = Integer.parseInt(stM.nextToken()); // 노드 b
int c = Integer.parseInt(stM.nextToken()); // 비용
int[] leftDirec = new int[] {b, c}; // {다음 노드, 비용}
int[] rightDirec = new int[] {a, c}; // {다음 노드, 비용}
graph[a].add(leftDirec);
graph[b].add(rightDirec);
}
// 비용의 오름차순으로 구성되는 우선순위 큐
PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return Integer.compare(o1[1], o2[1]);
}
});
// 방문 여부 기록 배열 선언 및 초기화
boolean[] isVisited = new boolean[N+1];
for (int i = 0; i < N+1; i++) {
isVisited[i] = false;
}
// 시작점 설정, 아무 값이나 상관 없음
int startPoint = 1;
int[] start = new int[] {startPoint, 0};
pq.add(start);
int totalCost = 0; // 사용한 비용 기록
// 만약 방문했던 노드라면 넘어감
// 만약 방문하지 않았던 노드라면 새로 연결하고, 그 노드의 엣지들을 다 큐에 넣는다.
while (!pq.isEmpty()) {
int[] now = pq.poll(); // {노드 번호, 비용}
if (isVisited[now[0]]) continue;
isVisited[now[0]] = true;
totalCost += now[1];
for (int[] next : graph[now[0]]) {
if (isVisited[next[0]]) continue;
pq.add(next);
}
}
// 정답 출력
System.out.println(totalCost);
}
}회고
알고리즘을 정확하게 이해하지 못해서 프림 알고리즘에서 연결 여부를 확인할 때 유니온 파인드를 사용했었다.
이렇게 해도 물론 풀이가 되긴 하지만 프림 알고리즘의 원리가 트리의 노드를 하나씩 확장하는 것이기 때문에 유니온 파인드 대신 방문 여부로 충분히 연결 여부를 확인할 수 있어 유니온 파인드를 사용하는게 비용적으로 손해다.
크루스칼 알고리즘에서는 진행 과정에서 여러 부분 그래프가 나타날 수 있기 때문에 방문 여부로 연결 여부를 알 수 없어 유니온 파인드를 사용하는 것이다.
