원더랜드 (Prim 알고리즘 응용)

개요 어제 풀었던 문제와 같은 문제로 그땐 쿠르스칼 알고리즘으로 최소 신장 트리를 구현했지만 이번엔 우선순위 큐와 그래프 탐색 방법 중 하나인 DFS를 통해 Prim 알고리즘을 응용해보았다. 원더랜드 문제 설명 원더랜드에 문제가 생겼다.

원더랜드의 각 도로를 유지보수하는 재정이 바닥난 것이다. 원더랜드... blog.naver.com 소스 코드 프림 알고리즘 개요.

출처: https://toastfactory.tistory.com/184 그래프를 순회하기 때문에 여타 그래프 탐색 알고리즘처럼 Visited로 정점에 재방문을 방지해줘야 된다. #include #include #include #include using namespace std; struct way { int to; int dis; bool operator()(way& a, way& b) { return a.dis > b.dis; } }; vector...