[BOJ] 백준 6497번 : 전력난 (JAVA)

문제

성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들어가는데, 일부를 소등하여 그만큼의 돈을 절약할 수 있다.

 

그러나 만약 어떤 두 집을 왕래할 때, 불이 켜져 있지 않은 길을 반드시 지나야 한다면 위험하다. 그래서 도시에 있는 모든 두 집 쌍에 대해, 불이 켜진 길만으로 서로를 왕래할 수 있어야 한다.

 

위 조건을 지키면서 절약할 수 있는 최대 액수를 구하시오.

 

 

입력

입력은 여러 개의 테스트 케이스로 구분되어 있다.

각 테스트 케이스의 첫째 줄에는 집의 수 m과 길의 수 n이 주어진다. (1 ≤ m ≤ 200000, m-1 ≤ n ≤ 200000)

 

이어서 n개의 줄에 각 길에 대한 정보 x, y, z가 주어지는데, 이는 x번 집과 y번 집 사이에 양방향 도로가 있으며 그 거리가 z미터라는 뜻이다. (0 ≤ x, y < m, x ≠ y)

도시는 항상 연결 그래프의 형태이고(즉, 어떤 두 집을 골라도 서로 왕래할 수 있는 경로가 있다), 도시상의 모든 길의 거리 합은 231미터보다 작다.

 

입력의 끝에서는 첫 줄에 0이 2개 주어진다.

 

 

출력

각 테스트 케이스마다 한 줄에 걸쳐 절약할 수 있는 최대 비용을 출력한다.

 

 

풀이

크루스칼 알고리즘을 사용하여 풀 수 있는 문제였습니다.

문제에서는 절약한 금액을 요구했으므로 전체 비용에서 크루스칼 알고리즘으로 구한 최소 비용을 뺀 값을 출력하면 됩니다.

 

다만, 제 블로그를 찾아오신 분은 위 알고리즘을 몰라서 찾아오신 것은 아닐겁니다.

아마, 대략 50% 정도에서 틀렸거나 런타임 에러가 뜬 경우일 것이라 생각합니다.

 

문제에서 입력 부분을 유심히 살펴봅시다.

"입력은 여러 개의 테스트 케이스로 구분되어 있다." 이 부분이 핵심입니다.

 

즉, N과 M이 각각 0이 아닐 때까지 무한루프를 돌리면서 각각에 대해 하나씩 절약된 비용을 출력하는 방식으로 구현하셔야합니다.

 

아래 코드를 통해 확인해 보시길 바랍니다.

 

 

소스코드

	import java.io.BufferedReader;
	import java.io.BufferedWriter;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.io.OutputStreamWriter;
	import java.util.ArrayList;
	import java.util.Collections;
	import java.util.StringTokenizer;
	class Edge implements Comparable<Edge> {
	int start;
	int end;
	int weight;
	Edge(int start, int end, int weight) {
	this.start = start;
	this.end = end;
	this.weight = weight;
	}
	@Override
	public int compareTo(Edge o) {
	return weight - o.weight;
	}
	}
	public class Main {
	static int[] parent;
	static ArrayList<Edge> edgeList;
	public static void main(String[] args) throws NumberFormatException, IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	StringTokenizer st;
	while (true) {
	st = new StringTokenizer(br.readLine());
	int M = Integer.parseInt(st.nextToken());
	int N = Integer.parseInt(st.nextToken());
	if (M == 0 && N == 0) {
	break;
	}
	edgeList = new ArrayList<>();
	int cost = 0; // 전체 비용
	for (int i = 0; i < N; i++) {
	st = new StringTokenizer(br.readLine());
	int x = Integer.parseInt(st.nextToken());
	int y = Integer.parseInt(st.nextToken());
	int z = Integer.parseInt(st.nextToken());
	edgeList.add(new Edge(x, y, z));
	cost += z;
	}
	Collections.sort(edgeList);
	parent = new int[M];
	for (int i = 0; i < M; i++) {
	parent[i] = i;
	}
	int minCost = 0; // 최소 비용
	for (int i = 0; i < edgeList.size(); i++) {
	Edge edge = edgeList.get(i);
	if (find(edge.start) != find(edge.end)) {
	minCost += edge.weight;
	union(edge.start, edge.end);
	}
	}
	bw.write((cost - minCost) + "\n"); // 절약된 비용
	}
	bw.flush();
	bw.close();
	br.close();
	}
	public static int find(int x) {
	if (x == parent[x]) {
	return x;
	}
	return parent[x] = find(parent[x]);
	}
	public static void union(int x, int y) {
	x = find(x);
	y = find(y);
	if (x != y) {
	parent[y] = x;
	}
	}
	}

view raw 6497.java hosted with ❤ by GitHub

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.