[대표 유형] 프림 알고리즘

문제 설명

정점의 개수 n, 양방향 간선 정보가 담긴 edges가 매개 변수로 주어질 때 프림 알고리즘을 적용하여 1번 정점부터 시작하여 최소 신장 트리에 포함되는 정점 번호를 순서대로 반환하는 solution 함수를 작성하시오.

만일 프림 알고리즘을 적용하던 과정에서 동일한 거리의 정점이 여러 개라면 정점 번호가 작은 정점을 먼저 탐색하시오.

그래프는 연결그래프(임의의 두 정점 사이에 경로가 존재하는 그래프)만 주어진다고 가정합니다.
그래프는 항상 최소 신장 트리가 존재하는 경우만 주어진다고 가정합니다.

개념 설명

최소 신장 트리(Minimum Spanning Tree)는 주어진 양방향 그래프에 대하여 간선의 가중치 총합이 최소인 신장 트리를 의미합니다.
참고 : [대표 유형] 최소 신장 트리

최소 신장 트리를 구하는 알고리즘으로는 프림 알고리즘과 크루스칼 알고리즘이 있습니다.

프림 알고리즘은 다음과 같은 과정으로 진행됩니다.

1. 임의의 정점 하나를 시작점으로 하여 집합 S에 포함합니다.
2. S에 포함되지 않은 정점들에 대해 S와 떨어진 거리를 계산합니다.
3. S에 포함되지 않은 정점 중 S와 떨어진 거리가 가장 작은 정점과 간선을 각각 S와 MST에 추가합니다.
4. 모든 정점이 S에 포함될 때까지 2, 3 과정을 반복합니다.

프림 알고리즘의 구현은 2가지 방법이 있습니다.

리스트를 사용한 방법으로는 O(V^2), 최소 힙을 사용한 방법은 O(E log V)의 시간 복잡도를 갖습니다.

예를 들어 다음과 같은 연결그래프가 있고 정점 1에서 프림 알고리즘을 시작한다고 가정합니다.

이때 S, MST, S와 각 정점 사이의 거리는 다음과 같이 초기화됩니다.

이후 S와의 거리가 최소인 정점은 2번 정점이므로 2번 정점을 S에 추가하고 그 간선의 길이를 MST 가중치 총합에 더합니다.

이후 추가한 2번 정점에 대해 연결된 간선을 바탕으로 S와의 거리를 새롭게 갱신합니다.

동일한 방법으로 3번 정점을 S에 추가하고 간선의 길이를 MST에 더한 뒤, S와의 거리를 갱신합니다.

이번에는 6번 정점이 S와의 거리가 가장 작으므로 S에 6번 정점을 추가하고 동일한 과정을 반복합니다.

S와 떨어진 거리가 동일한 정점이 여러 개 있다면 어느 정점을 S에 포함하여도 최소 신장 트리를 만드는 데에 지장이 없습니다.

이번 예시에서는 정점 번호가 작은 4번 정점을 S에 추가하고 알고리즘을 진행합니다.

마지막으로 5번 정점을 S에 추가하여 모든 정점이 S에 포함되면 알고리즘을 종료합니다.

해당 예시에서 프림 알고리즘을 통해 계산된 최소 신장 트리의 가중치 총합은 14입니다.

제한 사항

• 정점의 개수 n은 2 이상 5,000 이하의 자연수입니다.
• 양방향 간선 정보 edges의 원소는 특정 간선의 양 끝 정점 x, y와 간선의 가중치 w로 이루어집니다.
  • edges는 최대 1,000,000개의 간선 정보로 이루어집니다.
  • x, y는 1 이상 n 이하의 자연수입니다.
  • w는 10,000 이하의 자연수입니다.

예시 테스트케이스 설명

1번 테스트케이스 설명

• 위에서 제시된 예시와 동일합니다.

2번 테스트케이스 설명

• 주어진 그래프는 트리이며 1번 정점에서 3번, 2번 정점이 차례대로 최소 신장 트리에 추가되며 4번 정점과 5번 정점의 경우 동일한 간선의 가중치를 갖지만 정점 번호가 작은 4번이 먼저 최소 신장 트리에 추가됩니다.