[파이썬] 백준 20390 : 완전그래프의 최소 스패닝 트리 (골드1)

[파이썬] 백준 20390 : 완전그래프의 최소 스패닝 트리 (골드1)

• https://www.acmicpc.net/problem/20390

---

풀이

방향성 생각

• 메모리 제한 있는줄 모르고 크루스칼 했더니 메모리 초과.
• 범위만 보면 $O(NlogN)$ ~ $O(N^2)$까지 가능하다.
• 항상 MST 구성에서는 크루스칼 써서 프림 알고리즘 배우면서 프림 알고리즘으로 풀이.
• 메모리 제한 때문에 힙 쓰는 방식 대신 $O(NlogN)$으로 풀이.
•  

 

---

전체코드

import sys

input = sys.stdin.readline
INF = float('inf')

N = int(input())
A,B,C,D = map(int,input().split())
X = list(map(int,input().split()))


# MST seed : node 0
V = [False]*N
dist = [INF]*N
dist[0] = 0
answer = 0
for _ in range(N):

    # 3. 현재까지 MST 중 거리가 가장 작은 간선 선택하기
    x = -1
    cost = INF
    for i in range(N):
        if not V[i] and dist[i] < cost:
            cost = dist[i]
            x = i

    # 1. MST 연결 후, 간선 추가하기
    V[x] = True
    answer += cost

    # 2. node 0에서 시작해서
    for nx in range(N):
        if not V[nx]:
            ncost = ((X[min(x,nx)]*A+X[max(x,nx)]*B)%C)^D
            if ncost < dist[nx]:
                dist[nx] = ncost

print(answer)

코멘트

• 내부 for문의 순서를 다시 생각해보면 좋다.
  1. 현재 0에서 출발해서 answer에 cost를 추가한다.
  2. 현재 스패닝 트리에서 가장 가까운 거리를 dist에 업데이트한다.
     • 스패닝 트리가 연결되면서 현재까지 스패닝 트리와 다른 노드까지 거리 dist와 새로 추가된 node nx에서 거리 ncost랑 비교를 한다.
     • 이 과정에서 dist 배열에는 항상 스패닝 트리와의 최소값이 기록된다.
     • 이 배열을 사용하지 않으면 $O(N^3)$이라 시간초과.
  3. 현재 스패닝 트리와 거리가 가장 가까운 간선을 선택한다.
     1. 다시 1번으로 돌아가서 반복