BOJ 1916 최소비용 구하기 - Min Heap 을 직접 구현

 

제공되는 priority queue 를 사용하는 대신 Min Heap 을 직접 구현해서 최단 경로 문제를 풀어보았다. 

문제 링크 : https://www.acmicpc.net/problem/1916

1916번: 최소비용 구하기

 

pos 배열은 정점의 번호를 heap 내부의 위치로 바꾸어 준다.

 

x=pos[id];

 

이 코드는 id 정점이 heap 의 x 위치에 해당된다는 뜻이다.

pos 에 대해 일종의 역함수인  rev 배열은 heap 의 위치에 대응되는 정점의 번호를 되돌려준다. 

 

 

속도 면에서는 priority queue 보다 늦을 리는 없지만 구현이 지저분하다.

간결하게 만들도록 고민해 볼 것!