728x90
반응형
1647 - 도시 분할 계획
https://www.acmicpc.net/problem/1647

문제
마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이뤄짐
길은 어느 방향으로든지 다닐 수 있고 길을 유지하는데 드는 유지비 있음
마을을 2개의 분리된 마을로 분할할 계획
-> 분할 시 각 분리된 마을 안에 집들이 서로 연결 = 각 분리된 마을 안에 있는 임의의 두 집 사이 경로 항상 존재
/ 마을에 집이 하나 이상 있어야 함, 분리된 마을 사이 있는 길 없앨 수 있음
=> 길 모두 없애고 나머지 길의 유지비 합 최소
입력
첫째 줄: 집의 개수 N (2 <= N <= 100,000), 길의 개수 M (1 <= M <= 1,000,000)
다음 줄 ~ M줄: 길의 정보 A B C (1 <= C <= 1,000) (A번 집과 B번 집을 연결하는 길의 유지비 C)
(임의의 두 집 사이에 경로가 항상 존재하는 입력만 주어짐)
출력: 없애고 남은 길 유지비의 합의 최솟값
풀이
- Kruskal 알고리즘 (최소 신장 트리, MST)
- 간선을 비용 기준 오름차순으로 정렬
- Union-Find로 사이클 생기지 않게 연결
- `union(e.a, e.b)`
- 모든 정점 연결하면서 최소 비용 유지
- 가장 비싼 간선 하나 제공
- MST 만들면 전체 연결됨
- 비용 작은 간선부터 선택해서 전체 연결
- 한 개의 간선 제거 -> 두 개의 마을로 분리
- 최솟값 = 전체 비용 - 가장 큰 간선 비용
- `total += e.cost`
- `maxCost = e.cost`: 순서 정렬 -> 마지막 간선 비용이 가장 큰 비용
- MST 만들면 전체 연결됨
코드
import java.io.*;
import java.util.*;
// 도시 분할 계획
public class boj_1647 {
static int N, M;
static int[] unf;
static class Edge implements Comparable<Edge> {
int a, b, cost;
public Edge(int a, int b, int cost) {
this.a = a;
this.b = b;
this.cost = cost;
}
@Override
public int compareTo(Edge o) {
return cost - o.cost;
}
}
static int find(int v) {
if (v == unf[v]) return v;
return unf[v] = find(unf[v]);
}
static void union(int a, int b) {
int fa = find(a);
int fb = find(b);
if (fa != fb) unf[fb] = fa;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
List<Edge> edges = new ArrayList<>();
for (int i = 1; i <= M; i++) {
st = new StringTokenizer(br.readLine());
int A = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
int C = Integer.parseInt(st.nextToken());
edges.add(new Edge(A, B, C));
}
Collections.sort(edges);
unf = new int[N + 1];
for (int i = 1; i <= N; i++) unf[i] = i;
int total = 0;
int maxCost = 0;
for (Edge e : edges) {
if (find(e.a) != find(e.b)) {
union(e.a, e.b);
total += e.cost;
maxCost = e.cost;
}
}
System.out.println(total - maxCost);
}
}728x90
반응형
'✏️ > BOJ' 카테고리의 다른 글
| [BOJ/DFS+BFS] 백준 14502 - 연구소 (Java) (0) | 2025.11.12 |
|---|---|
| [BOJ/Dijkstra] 백준 1504 - 특정한 최단 경로 (Java) (0) | 2025.11.11 |
| [BOJ] 백준 2252 - 줄 세우기 (Java) (0) | 2025.11.11 |
| [BOJ/DFS+DP] 백준 2533 - 사회망 서비스(SNS) (Java) (0) | 2025.11.10 |
| [BOJ/BFS] 백준 16954 - 움직이는 미로 탈출 (Java) (0) | 2025.11.10 |