1197

날짜 : 2023. 03. 27

사용 언어 : python

 

문제

 

 

코드

import sys

v, e = map(int, sys.stdin.readline().split())  # 정점의 개수, 간선의 개수
parent = [i for i in range(v + 1)]  # 각 노드의 부모
edges = []


# find 연산(parent 최신화)
def parent_find(parent, x):
    if parent[x] != x:  # 본인노드 부모가 자신이 아니라면
        parent[x] = parent_find(parent, parent[x])  # 최신화
    return parent[x]


def parent_union(parent, a, b):
    a = parent_find(parent, a)
    b = parent_find(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b


for _ in range(e):
    a, b, c = map(int, sys.stdin.readline().split())  # 시작, 도착, 가중치
    edges.append((c, a, b))

# 간선 정보 정렬(cost 작은 간선부터 체크)
edges.sort()
total = 0

for i in range(e):
    cost, a, b = edges[i]  # cost 가 작은 노드부터 통합
    if parent_find(parent, a) != parent_find(parent, b):  # a, b간 사이클 확인
        parent_union(parent, a, b)  # 사이클 없는 경우 union
        total += cost

print(total)

 

 

풀이

- 플로이드-워셜을 활용해서 풀이하려 했지만 3%에서 계속 메모리 초과가 발생했다.

- 최소 스패닝 트리를 풀이하는 문제의 경우에는 Prim과 Kruskal 알고리즘을 활용해서 풀이해야 했다.

- 전형적인 Kruskal 알고리즘을 활용해서 풀이하는 문제였다.

- edge의 정보를 cost 오름차순으로 정렬 후 해당 edge를 넣었을 때의 사이클 유무를 판별한 이후, 사이클이 없다면 각 노드의 parent를 최신화하여 집합을 만든다.

- 그리고 이 과정을 모든 edge에 대하여 돌린 다음 결과값을 출력하면 끝

 

 

알게된 점

- Kruskal을 포함한 최소신장트리 관련 알고리즘을 까먹은 바람에 문제를 풀이하지 못한 케이스였다.

- 조만간 MST 관련 문제들을 많이 풀어봐야겠다.

 

 

참고 사이트

- https://techblog-history-younghunjo1.tistory.com/262

[Python] 최소 신장 트리를 찾는 크루스칼(Kruskal) 알고리즘