문제
도현이는 컴퓨터와 컴퓨터를 모두 연결하는 네트워크를 구축하려 한다. 하지만 아쉽게도 허브가 있지 않아 컴퓨터와 컴퓨터를 직접 연결하여야 한다. 그런데 모두가 자료를 공유하기 위해서는 모든 컴퓨터가 연결이 되어 있어야 한다.
(a와 b가 연결이 되어 있다는 말은 a에서 b로의 경로가 존재한다는 것을 의미한다. a에서 b를 연결하는 선이 있고, b와 c를 연결하는 선이 있으면 a와 c는 연결이 되어있다)
그런데 이왕이면 컴퓨터를 연결하는 비용을 최소로 하여야 컴퓨터를 연결하는 비용 외에 다른 곳에 돈을 더 쓸 수 있을 것이다. 이제 각 컴퓨터를 연결하는데 필요한 비용이 주어졌을 때 모든 컴퓨터를 연결하는데 필요한 최소 비용을 출력하라
해당 문제를 풀려면 먼저 크루스칼 알고리즘에 대해 알아야 하낟.
크루스칼 알고리즘
- 최소 비용 신장트리를 찾는 알고리즘이다.
- 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘이다.
이정도면 이 문제를 풀 수 있다.
이제 흐름을 파악하자
1. 간선의 가중치를 오름차순으로 정렬한다. (Edge 클래스를 통해 start,end,cost를 한 번에 받는다)
2. 정렬된 간선 중에서 순서대로 Edge를 조회한다.
- 이 과정에서 사이클이 형성된다면 다음 간선으로 넘어간다. 사이클이 안 생기면 해당 간선을 선택한다
여기서 해당 노드의 부모를 찾아야 한다. 그래서 parent[] 라는 배열이 필요하고 해당 배열을 자신의 노드는 자신을 바라보도록 바꾼다 -> 1번 인덱스 1 , 2번 인덱스 2 ..... N
그 다음 입력 값들을 전부 받아야 한다.
가중치 순으로 오름차순으로 정렬을 하고
정렬된 값들을 전부 순회한다. 해당 과정에서 find를 통해 부모를 찾는데 만약 부모가 같은 경우 사이클이기 떄문이 그냥 통과하고 같지 않다는 것은 사이클이 아니라서 union을 통해 간선을 연결한다.
해당 find 메소드가 자신의 부모를 찾는다. 간선이 모두 연결이 되지 않은 상태면 parent 배열은 모두 자신을 가리키고 있으므로 재귀하지 않을 것이다. 하지만 union을 통해 parent는 변경된다.
처음 Edge(2,3,2) 가들어온다고 치면 parent의 2번 인덱스는 2고, 3번 인덱스는 3이다. 그렇게 두 Edge는 연결된다.
parent[3] = 2가 되고 이런식으로 계속 연결되는 것이다.
근데 여기서 다른 간선이 3이랑 연결이 된다면 find 메소드가 실행되고 find메소드에 파라미터로 3이 전달되면 parent[3]과 3은 다른 값이기 때문에 재귀로 들어간다. 그러면서 바로 parent[3]인 2가 파라미터로 들어가면서 2를 리턴한다.
결국 3이랑 해당 값은 연결되게 된다. (1,3)이었을 경우 parent[2] = 1로 변경된다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int parent[];
static ArrayList<Edge> graph;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int total = 0;
int N = Integer.parseInt(br.readLine());
int M = Integer.parseInt(br.readLine());
parent = new int[N+1];
graph = new ArrayList<>();
for (int i = 1; i <= N; i++) {
parent[i] = i;
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
int cost = Integer.parseInt(st.nextToken());
graph.add( new Edge(start,end,cost));
}
Collections.sort(graph,new Comparator<Edge>(){
@Override
public int compare(Edge o1, Edge o2) {
return o1.cost - o2.cost;
}
});
for (int i = 0; i < graph.size() ; i++) {
Edge edge = graph.get(i);
if(find(edge.start) != find(edge.end)){
total += edge.cost;
union(edge.start, edge.end);
}
}
System.out.println(total);
}
public static void union(int x, int y){
x = find(x);
y = find(y);
if(x != y){
parent[y] = x;
}
}
public static int find(int x){
if(x == parent[x]){
return x;
}
return parent[x] = find(parent[x]);
}
static class Edge{
public int start;
public int end;
public int cost;
public Edge(int start,int end, int cost){
this.start = start;
this.end = end;
this.cost = cost;
}
}
}