1197번 - 최소 스패닝 트리
문제 풀이 시간 : 1시간
문제 요약
- 그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하라
- 정점의 개수 V (1 ≤ V ≤ 10,000)
- 간선의 개수 E (1 ≤ E ≤ 100,000)
- E 개의 줄에 각 간선에 대한 정보 A, B, C 가 주어진다.
- A 번과 B 번 정점이 가중치가 C 인 간선으로 연결되었다는 것을 나타낸다.
문제 풀이
이거는 그냥 알고리즘 수업시간때 배웠던 쿠르스칼 알고리즘을 한번 구현해보려고 풀었다.
쿠르스칼은 가중치가 가장 작은 간선을 순서대로 선택하기 때문에 간선의 가중치를 중심으로 먼저 정렬을 해주었다.
Arrays.sort(graph, new Comparator<Node>() {
@Override
public int compare(Node o1, Node o2) {
return o1.c-o2.c;
}
});그리고 Union - Find 를 활용해서 각 노드가 같은 트리에 있는지 확인하면서
같은 트리에 없다면 해당 간선을 추가해주는 방식으로 진행해주었다.
특히, find 에서 더욱 효율적인 탐색을 위해 새롭게 찾은 부모 노드의 정보를 업데이트 해주어
다음 탐색에서 더 빠르게 찾을 수 있도록 하였따.
public static int find(int a){
if(parent[a]!=a){
parent[a] = find(parent[a]);
}
return parent[a];
}
초기 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.security.Provider;
import java.util.*;
public class Main {
public static int V, E;
public static Node[] graph;
public static int[] parent;
public static class Node{
private final int a;
private final int b;
private final int c;
public Node(int a,int b,int c){
this.a = a;
this.b = b;
this.c = c;
}
}
public static int find(int a){
if(parent[a]!=a){
parent[a] = find(parent[a]);
}
return parent[a];
}
public static void union(int a, int b){
int rootA = find(a);
int rootB = find(b);
if(rootA!=rootB){
parent[rootB] = rootA;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
V = Integer.parseInt(st.nextToken());
E = Integer.parseInt(st.nextToken());
parent = new int[V];
graph = new Node[E];
for(int i=0;i<E;i++){
st = new StringTokenizer(br.readLine());
Node input = new Node(Integer.parseInt(st.nextToken())-1,Integer.parseInt(st.nextToken())-1,Integer.parseInt(st.nextToken()));
graph[i]=input;
}
for(int i=0;i<V;i++){
parent[i]=i;
}
Arrays.sort(graph, new Comparator<Node>() {
@Override
public int compare(Node o1, Node o2) {
return o1.c-o2.c;
}
});
long result = 0L;
for(int i=0;i<E;i++){
Node temp = graph[i];
int p1 = find(temp.a);
int p2 = find(temp.b);
if(p1==p2){
continue;
}
result += temp.c;
union(temp.a, temp.b);
}
System.out.println(result);
}
}함께 읽으면 좋은 글
5430번 - AC
함수 R은 배열을 뒤집는 연산 함수 D는 첫 번째 원소를 버리는 연산 단, 배열이 비어 있을 때 D를 수행하면 error 주어진 함수 문자열을 순서대로 수행한 뒤 최종 배열을 출력하는 문제 처음에는 문제 설명 그대로 R이 나올 때마다 배열을 실제로 뒤집고, D가 나오면 맨 앞…
1966번 - 프린터 큐
여러 문서가 큐에 들어 있고, 각 문서마다 중요도가 있음 맨 앞 문서를 확인했을 때, 더 높은 중요도의 문서가 뒤에 하나라도 있으면 맨 뒤로 보냄 그렇지 않으면 바로 인쇄 특정 위치의 문서가 몇 번째로 인쇄되는지 구하는 문제 이 문제는 프린터의 동작을 그대로 구현하면 되는…
1158 - 요세푸스 문제
1번부터 N번까지 사람이 원형으로 앉아 있음 순서대로 K번째 사람을 제거 모든 사람이 제거될 때까지 반복 제거되는 순서를 출력하는 문제 이 문제는 원형으로 순회하면서 K번째를 제거하는 과정을 그대로 구현하면 된다.
2164번 - 카드2
1부터 N까지 카드가 순서대로 쌓여 있음 맨 위 카드를 버리고, 그다음 맨 위 카드를 맨 아래로 옮기는 과정을 반복 마지막에 남는 카드 번호를 구하는 문제 이 문제는 규칙을 찾기보다, 문제에서 하라는 과정을 그대로 구현하면 된다. 카드 더미에서 반복되는 동작은 두 가지다.