728x90
1. 문제
1197번: 최소 스패닝 트리
첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이
www.acmicpc.net
그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.
최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.
2. 풀이
유니온 파인드를 이용해서 크루스칼 알고리즘을 구현했다.
간선의 가중치 순으로 정렬해서, 그 간선을 그래프에 추가할 수 있다면(사이클이 일어나지 않는다면) 합치고 answer에 가중치를 더한다.
import java.io.*;
import java.util.*;
public class BOJ_1197_최소스패닝트리 {
static int[] root;
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(in.readLine());
int V = Integer.parseInt(st.nextToken());
int E = Integer.parseInt(st.nextToken());
root = new int[V+1];
for(int i=1;i<=V;i++) root[i] = i;
PriorityQueue<int[]> pq = new PriorityQueue<>((o1,o2)->o1[2]-o2[2]);
int a,b,c;
for(int i=0;i<E;i++){
st = new StringTokenizer(in.readLine());
a = Integer.parseInt(st.nextToken());
b = Integer.parseInt(st.nextToken());
c = Integer.parseInt(st.nextToken());
pq.offer(new int[]{a,b,c});
}
int answer = 0;
while(!pq.isEmpty()){
a = find(pq.peek()[0]);
b = find(pq.peek()[1]);
c = pq.poll()[2];
if(a == b) continue;
union(a,b);
answer += c;
}
System.out.println(answer);
}
private static int find(int x){
if(root[x]==x) return x;
return root[x] = find(root[x]);
}
private static void union(int a,int b){
int ra = find(a);
int rb = find(b);
if(ra==rb) return;
root[ra] = rb;
}
}
3. 결과
우선순위 큐 사용 - 리스트 사용 - 리스트 사용 - 우선순위 큐 사용
이런 식으로 방식을 바꿔봤는데 큰 차이는 나지 않았다.
'코딩테스트 > BOJ' 카테고리의 다른 글
[BOJ] 14725 개미굴 - JAVA (0) | 2023.05.31 |
---|---|
[BOJ] 15904 UCPC는 무엇의 약자일까? - JAVA (0) | 2023.05.30 |
[BOJ] 3055 탈출 - JAVA (1) | 2023.05.27 |
[BOJ] 1300 K번째 수 - JAVA (0) | 2023.05.26 |
[BOJ] 14888 연산자 끼워넣기 - JAVA (0) | 2023.05.25 |
댓글