6497. 전력난 (코딩테스트, 백준, 자바)

문제

6497번: 전력난

---

나의 풀이

• 두 집 사이에 왕래를 하려면 반드시 길을 지나야 하며 길을 지나기 위해서는 불이 켜져있어야 한다.
• 불이 켜진 길은 거리만큼의 비용이 든다.
• 모든 집이 왕래가 가능해야 하기때문에 고립되어 있는 집이 없도록 해야 한다.
• 모든 선에는 비용정보가 있다. -> 모두가 연결되어 고립되지 않도록 하되 선들의 비용합이 최소를 선택
• 집 수 -1 <= 길의 수 <= 20만 이며  집과 길의 수는 20만을 넘지 않는다.

입력값 분석 -> 끝나는 줄을 표시하는 0 0 을 만나지 않는다면 새로운 테스트케이스가 시작한다는 것을 명심하자.

하나의 테스트로 끝나는 것이 아니다.

 

union-set 방법을 사용해서 각 그룹의 대표자를 표시하고 경로들에 대한 비용의 내림차순 순서대로 접근하면 

다음에 비용이 더 높은 길을 찾더라도 같은 그룹에 속한 상태에서는 무시하고 해당 길의 비용만큼 절약할 수 있다.

우선순위 큐로 내림차순 접근 가능

 

union-set 메소드 및 길을 표현하는 Point 클래스

answer의 초기값은 모든 길에 대한 비용들의 합산 선택된 길을 제외한 값 => 절약한 비용을 나타낸다.

 

---

나의 코드

GitHub - lyeong-gwa/algorithm_study: 알고리즘 공부!