링크
https://www.acmicpc.net/problem/1197
문제 설명
정답률 41.247%
그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.
최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.
입력 예제
- 첫째 줄에 정점의 개수 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보다 작거나 같은 데이터만 입력으로 주어진다.
3 3
1 2 1
2 3 2
1 3 3
출력 예제
- 첫째 줄에 최소 스패닝 트리의 가중치를 출력한다.
3
풀이
최소 신장 트리를 구하는 기본적인 문제이다. 최소 신장 트리란 그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리이다. 최소 신장 트리는 노드가 아닌 에지를 중심으로 저장하기 때문에 에지 객체를 만들기 위해 Edge 클래스를 생성한다.
static class Edge {
int from;
int to;
int weight;
public Edge(int from, int to, int weight) {
this.from = from;
this.to = to;
this.weight = weight;
}
public int getWeight() {
return weight;
}
}부모 노드를 노드 번호로 초기화하고 에지 리스트에 에지 정보를 저장한다.
//부모 노드 초기화
parents = new int[V + 1];
for (int i = 1; i <= V; i++) {
parents[i] = i;
}
//에지 리스트 초기화
List<Edge> edges = new ArrayList<>();
for (int i = 0; i < E; i++) {
st = new StringTokenizer(br.readLine());
int A = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
int C = Integer.parseInt(st.nextToken()); //가중치 (10^6)
edges.add(new Edge(A, B, C));
}가중치가 작은 에지부터 연결을 시도해야 하기 때문에 가중치를 기준으로 오름차순 정렬한다.
//에지의 가중치를 기준으로 오름차순 정렬
edges.sort(Comparator.comparingInt(Edge::getWeight));이제 가중치가 낮은 에지부터 연결을 시도한다. 이때 그래프의 사이클 형성 유무를 판단하기 위해 두 노드의 부모가 다를 때 연결한다. 그리고 에지의 개수가 노드의 개수 - 1이 되면 종료한다.
//모든 간선에 대하여 반복
for (int i = 0; i < E; i++) {
Edge cur = edges.get(i);
int from = cur.from;
int to = cur.to;
//시작 노드와 종료 노드가 부모 노드가 다를 경우
if (!check(from, to)) {
union(from, to);
result += cur.weight;
count++;
}
//간선의 개수가 V-1되면 중단
if (count == V - 1) {
break;
}
}코드
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.StringTokenizer;
//백준
public class Main {
static int[] parents;
public static void main(String[] args) throws IOException {
System.setIn(new FileInputStream("src/input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int V = Integer.parseInt(st.nextToken()); //정점의 개수 (10^4)
int E = Integer.parseInt(st.nextToken()); //간선의 개수 (10^5)
//부모 노드 초기화
parents = new int[V + 1];
for (int i = 1; i <= V; i++) {
parents[i] = i;
}
//간선 리스트 초기화
List<Edge> edges = new ArrayList<>();
for (int i = 0; i < E; i++) {
st = new StringTokenizer(br.readLine());
int A = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
int C = Integer.parseInt(st.nextToken()); //가중치 (10^6)
edges.add(new Edge(A, B, C));
}
//간선의 가중치를 기준으로 오름차순 정렬
edges.sort(Comparator.comparingInt(Edge::getWeight));
int result = 0;
int count = 0;
//모든 간선에 대하여 반복
for (int i = 0; i < E; i++) {
Edge cur = edges.get(i);
int from = cur.from;
int to = cur.to;
//시작 노드와 종료 노드가 부모 노드가 다를 경우
if (!check(from, to)) {
union(from, to);
result += cur.weight;
count++;
}
//간선의 개수가 V-1되면 중단
if (count == V - 1) {
break;
}
}
System.out.println(result);
}
static int find(int x) {
if (parents[x] == x) {
return x;
}
return parents[x] = find(parents[x]);
}
static void union(int a, int b) {
a = find(a);
b = find(b);
if (a < b) {
parents[b] = a;
} else {
parents[a] = b;
}
}
static boolean check(int a, int b) {
return find(a) == find(b);
}
static class Edge {
int from;
int to;
int weight;
public Edge(int from, int to, int weight) {
this.from = from;
this.to = to;
this.weight = weight;
}
public int getWeight() {
return weight;
}
}
}
백엔드