🔗 문제 링크
📝 문제 설명
전력난 문제는 여러 도시와 이들을 연결하는 도로들이 주어졌을 때,
모든 도시가 연결된 상태를 유지하면서 불필요한 도로의 전력 소비를 줄여
절약할 수 있는 전력의 총합을 구하는 문제입니다.
-
입력:
- 각 테스트 케이스마다 도시의 개수(N)와 도로의 개수(M)가 주어지며,
이후 각 도로에 대해 두 도시와 해당 도로의 비용이 주어집니다. - "0 0"이 입력되면 테스트 케이스 입력을 종료합니다.
- 각 테스트 케이스마다 도시의 개수(N)와 도로의 개수(M)가 주어지며,
-
출력:
- 전체 도로의 비용에서,
모든 도시가 연결되도록 선택한 최소 도로(최소 신장 트리, MST)를 구성하는 데 사용된 비용을 뺀
절약 가능한 전력의 총합을 출력합니다.
- 전체 도로의 비용에서,
✅ 접근 방식 및 해결 과정
MST와 Union-Find를 활용한 해결
문제의 핵심은 모든 도시를 연결하는 상태를 유지하면서,
불필요한 도로의 전력 소비를 제거하는 것입니다.
즉, 전체 도로 비용에서 MST를 구성하는 데 사용된 도로 비용을 빼면
절약 가능한 전력의 양을 구할 수 있습니다.
-
아이디어:
- 전체 도로 비용(
allSum)과 MST 도로 비용(mstSum)을 각각 구합니다. - 절약 가능한 전력은
allSum - mstSum으로 계산됩니다.
- 전체 도로 비용(
-
알고리즘 선택:
- Kruskal 알고리즘: 간선(도로)들을 비용 오름차순으로 정렬한 후,
Union-Find 자료구조를 사용해 사이클 없이 MST를 구성합니다. - Union-Find: 각 도시를 집합으로 관리하며, 경로 압축(Path Compression)을 통해 효율적으로 집합을 합칩니다.
- Kruskal 알고리즘: 간선(도로)들을 비용 오름차순으로 정렬한 후,
구현 단계
-
입력 처리 및 초기화:
- 각 테스트 케이스마다 도시 수(N)와 도로 수(M)를 입력받습니다.
- 각 도시는 자기 자신을 부모로 가지는 단일 집합으로 초기화합니다.
- 모든 도로 정보를 우선순위 큐에 비용 기준 오름차순으로 저장하며,
동시에 전체 도로 비용(allSum)을 누적합니다.
-
최소 신장 트리(MST) 구성:
- 우선순위 큐에서 비용이 가장 낮은 도로부터 하나씩 선택합니다.
- 두 도시가 서로 다른 집합에 속해 있다면 해당 도로를 MST에 포함시키고,
두 집합을 합칩니다. - 이 과정에서 사용된 도로 비용을 누적하여
mstSum을 구합니다.
-
절약 가능한 전력 계산:
- 전체 도로 비용(
allSum)에서 MST 구성 비용(mstSum)을 빼면,
절약할 수 있는 전력의 총합을 얻을 수 있습니다.
- 전체 도로 비용(
🔍 최종 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Main {
private static StringTokenizer st;
private static StringBuilder sb = new StringBuilder();
private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
private static int N, M;
private static PriorityQueue<int[]> pq;
private static int[] parent;
private static int allSum;
public static void main(String[] args) throws IOException {
/*
* 문제의 핵심은 모든 도시를 연결하는 상태를 유지하면서,
* 불필요한 도로를 제거해 절약할 수 있는 전력의 총합을 구하는 것입니다.
* 전체 도로 비용에서 MST 구성에 사용된 비용을 빼면,
* 절약 가능한 전력의 양을 구할 수 있습니다.
* 여기서는 Kruskal 알고리즘과 Union-Find 자료구조를 활용했습니다.
*/
while (true) {
if (!isSetting()) break;
sb.append(allSum - getMstSum()).append("\n");
}
System.out.println(sb.toString());
}
private static int getMstSum() {
int sum = 0;
while (pq.size() > 0) {
int[] cur = pq.poll();
int from = cur[0];
int to = cur[1];
int val = cur[2];
if (find(from) != find(to)) {
union(from, to);
sum += val;
}
}
return sum;
}
private static int find(int num) {
if (num == parent[num]) return num;
return parent[num] = find(parent[num]);
}
private static void union(int num1, int num2) {
int parent1 = find(num1);
int parent2 = find(num2);
if (parent1 < parent2) {
parent[parent2] = parent1;
find(num2); // 경로 압축을 통한 최적화
} else {
parent[parent1] = parent2;
find(num1); // 경로 압축을 통한 최적화
}
}
private static boolean isSetting() throws IOException {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
if (N == 0 && M == 0) return false; // 종료 조건
parent = new int[N];
for (int i = 0; i < N; i++) {
parent[i] = i;
}
pq = new PriorityQueue<>(Comparator.comparingInt(o -> o[2]));
allSum = 0;
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());
int val = Integer.parseInt(st.nextToken());
allSum += val;
pq.add(new int[]{from, to, val});
}
return true;
}
}🔍 코드 로직 상세 설명
-
입력 처리 및 초기화:
- 각 테스트 케이스마다 도시 수(N)와 도로 수(M)를 입력받고,
각 도시는 자기 자신을 부모로 가지는 단일 집합으로 초기화합니다. - 모든 도로 정보를 비용 기준 오름차순으로 정렬한 우선순위 큐에 저장하고,
전체 도로 비용(allSum)을 누적합니다.
- 각 테스트 케이스마다 도시 수(N)와 도로 수(M)를 입력받고,
-
최소 신장 트리(MST) 구성:
- 우선순위 큐에서 비용이 가장 낮은 도로부터 하나씩 선택하며,
두 도시가 서로 다른 집합에 속해 있다면 해당 도로를 MST에 포함시킵니다. - 이때 Union-Find 자료구조를 사용해 두 도시의 집합을 합치며,
사이클이 생기지 않도록 합니다. - MST 구성 시 사용된 도로 비용을 누적하여
mstSum을 구합니다.
- 우선순위 큐에서 비용이 가장 낮은 도로부터 하나씩 선택하며,
-
절약 가능한 전력 계산:
- 전체 도로 비용(
allSum)에서 MST 구성 비용(mstSum)을 빼면,
절약할 수 있는 전력의 총합을 얻을 수 있습니다.
- 전체 도로 비용(
멋있는 사람 - 일단 하자