[백준 / BOJ] 10423 전기가 부족해 (다익스트라)

문제

출처 : www.acmicpc.net/problem/10423

10423번: 전기가 부족해

K개의 발전소, N개의 도시, M개의 케이블수가 주어졌을때, 발전소에서 시작해서 모든도시까지 전기를 공급하는 문제다.

 

풀이

입력받은 발전소들을 시작지점으로해서 다익을 돌리면된다.

 

예를들어, 발전소가 3개일경우 다익의 시작지점은 총 3개가 된다.

 

코드를 짜면서 몇가지 반례?가 될수있는걸 생각해봤는데, 도시와 발전소 사이에 발전소가 존재할경우..?

 

발전소 N

도시 A

발전소 B

 

(N -> B -> A) 이렇게 연결되어있다면 A까지 가는 최소연결비용은 당연히 B에서 시작하는게 적게든다. 따라서 예외처리 해줄필요가 없었다,, 이게 별거 아닌것처럼 보여도 내 풀이의 핵심 아이디어가 됐다. 

한 발전소에서 도시까지 가는경로는 다른 발전소를 거쳐 오는것보다 한번에 가는것이 항상 가까우므로, 최소 연결 간선을 priority_queue를 사용해서 구현하면 시간이 많이 줄어들것이라고 생각했다.

 

1. 발전소 위치 pq에 넣기 (pq는 greater 정렬되어있음)

2. pq.top()참조하면서 가장작은 간선부터 탐색

 

전기를 전달하지 않은 도시에 대해서만, 1,2번을 반복하면 답.

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/10423%20%EC%A0%84%EA%B8%B0%EA%B0%80%20%EB%B6%80%EC%A1%B1%ED%95%B4/main.cpp

devxb/JJUNalgo