[Gold IV] 최소 스패닝 트리 - 1197
성능 요약
메모리: 230420 KB, 시간: 1196 ms
분류
그래프 이론(graphs), 최소 스패닝 트리(mst)
문제 설명
그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.
최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.
입력
첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.
그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 트리의 가중치가 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다.
출력
첫째 줄에 최소 스패닝 트리의 가중치를 출력한다.
최소 스패닝 트리를 구할 수 있는 두 가지 알고리즘 (프림, 크루스칼)을 사용하여 풀었다.
https://code-master-s.tistory.com/151
1. 프림 알고리즘
Edge 클래스를 w를 기준으로 정렬하도록 만들었다.
static class Edge implements Comparable<Edge> {
int st;
int ed;
long w;
public Edge(int st, int ed, long w) {
this.st = st;
this.ed = ed;
this.w = w;
}
@Override
public int compareTo(Edge o) {
return Long.compare(this.w, o.w);
}
}
그래프의 edge는 인접 리스트로 구현하였고, PriorityQueue를 이용해 prim 알고리즘을 진행했다.
전체 코드
package Gold.g4;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;
public class BOJ_1197_최소스패닝트리_prim {
static class Edge implements Comparable<Edge> {
int st;
int ed;
long w;
public Edge(int st, int ed, long w) {
this.st = st;
this.ed = ed;
this.w = w;
}
@Override
public int compareTo(Edge o) {
return Long.compare(this.w, o.w);
}
}
static int V, E;
static List<Edge>[] adjList;
static boolean[] visited;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
V = sc.nextInt();
E = sc.nextInt();
adjList = new ArrayList[V + 1];
for (int i = 0; i <= V; i++)
adjList[i] = new ArrayList<>();
visited = new boolean[V + 1];
for (int i = 0; i < E; i++) {
int st = sc.nextInt();
int ed = sc.nextInt();
int w = sc.nextInt();
adjList[st].add(new Edge(st, ed, w));
adjList[ed].add(new Edge(ed, st, w)); // 무향 그래프
}
// 1번부터 시작
visited[1] = true;
PriorityQueue<Edge> q = new PriorityQueue<>();
q.addAll(adjList[1]);
int pick = 0;
long ans = 0;
while (pick < V - 1) {
Edge e = q.poll();
if (visited[e.ed])
continue;
ans += e.w;
visited[e.ed] = true;
pick++;
for (int i = 0; i < adjList[e.ed].size(); i++) {
Edge tmp = adjList[e.ed].get(i);
if (!visited[tmp.ed])
q.add(tmp);
}
}
System.out.println(ans);
}
}
2. 크루스칼 알고리즘
Edge를 w기준으로 오름차순 정렬 후, w가 작은 노드부터 시작
edge의 시작점과 끝점이 cycle을 이루지 않으면 (findSet의 값이 같지 않다면) 해당 edge를 포함한다.
package Gold.g4;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
public class BOJ_1197_최소스패닝트리_kruskal {
static class Edge {
int st;
int ed;
long w;
public Edge(int st, int ed, long w) {
this.st = st;
this.ed = ed;
this.w = w;
}
}
static int V, E;
static Edge[] adjArr;
static int[] p;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
V = sc.nextInt();
E = sc.nextInt();
adjArr = new Edge[E];
for (int i = 0; i < E; i++) {
int st = sc.nextInt();
int ed = sc.nextInt();
int w = sc.nextInt();
adjArr[i] = new Edge(st, ed, w);
}
Arrays.sort(adjArr, new Comparator<Edge>() {
@Override
public int compare(Edge o1, Edge o2) {
return Long.compare(o1.w, o2.w);
}
});
p = new int[V + 1];
// make-set
for (int i = 1; i <= V; i++)
p[i] = i;
long ans = 0;
for (int i = 0; i < E; i++) {
int st = adjArr[i].st;
int ed = adjArr[i].ed;
long w = adjArr[i].w;
int setX = findSet(st);
int setY = findSet(ed);
if (setX != setY) {// cycle 아님
// union
p[setY] = p[setX];
ans += w;
}
}
System.out.println(ans);
}
static int findSet(int x) {
if (p[x] != x)
p[x] = findSet(p[x]);
return p[x];
}
}
'문제 풀이 > BOJ' 카테고리의 다른 글
[백준] 13549 - 숨바꼭질 3 (자바 Java) (0) | 2022.09.30 |
---|---|
[백준] 4195 - 친구 네트워크 (자바 Java) (0) | 2022.09.29 |
[백준] 11660 - 구간 합 구하기 (자바/Java) (1) | 2022.09.27 |
[백준] 16139 - 인간-컴퓨터 상호작용 (자바/Java) (0) | 2022.09.27 |
[백준] 11659 - 구간 합 구하기 4 (자바/Java) : 누적 합 (0) | 2022.09.27 |