[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이 아닐 때까지 무한루프를 돌리면서 각각에 대해 하나씩 절약된 비용을 출력하는 방식으로 구현하셔야합니다.

 

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

 

 

소스코드

 

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