[파이썬] 백준 16398 : 행성 연결 (골드4)

[파이썬] 백준 16398 : 행성 연결 (골드4)

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

---

풀이

방향성 생각

• 최소 비용으로 모든 노드 연결 -> MST 기본.
• 입력이 인접행렬식으로 주어진다.
  • 대칭이라서 순회만 상삼각으로 훑어준다.

---

전체코드

N = int(input())

# 상삼각 읽기
matrix = [tuple(map(int,input().split())) for _ in range(N)]
G = []
for i in range(N):
    for j in range(i+1,N):
        G.append((i,j,matrix[i][j]))
G.sort(key=lambda x:-x[2])

P = [i for i in range(N+1)]
def find(x):
    if P[x] != x:
        P[x] = find(P[x])
    return P[x]

answer = 0
while G:
    a,b,cost = G.pop()
    pa,pb = find(a),find(b)
    if pa!=pb:
        P[max(pa,pb)] = min(pa,pb)
        answer += cost
print(answer)

---

코멘트

• input이 작아서 큰 상관없는 문제지만, 입력이 큰 경우 node N개가 모두 연결됐을 경우 loop 탈출을 하면 효과적이다.