프림

[JAVA] 백준 1922 : 네트워크 연결

문제 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 풀이방법 한 정점에서 모든 정점을 연결하는데에 드는 비용을 최소로 하는 문제이다. 크루스칼과 프림을 사용할 수 있는데, 프림을 안써본지 오래되어서 프림으로 코드를 구성해보았다. 인접리스트로 양방향 연결을 먼저 해준다음 임의의 시작점에서 출발시키면된다. 프림은 방문배열과 각 정점의 최소비용을 저장할 정점 크기만큼의 1차원 배열을 사용한다. 최소비용을 저장할 배열은 최대값으로 초기화해준다. 필자는 우선순위큐를 활용한 프림을 구성하였는데, 그렇기 때문에 비용에 따라 오름차순 정렬을 통해 비용이 적은 것 부터 탐색하도록하였다. 임의의 시작 정점을 정하였..