1922

날짜 : 2023. 04. 29

사용 언어 : python

 

문제

https://www.acmicpc.net/problem/1922

 

 

코드

import sys
def find(parent, p):  # 집합의 부모 리턴
    if parent[p] != p:
        parent[p] = find(parent, parent[p])
    return parent[p]


def union(a, b):
    # 각 노드의 부모 구하기
    a = find(parent, a)
    b = find(parent, b)
    if a < b:  # 작은걸로 설정
        parent[b] = a
    else:
        parent[a] = b
    return

n = int(sys.stdin.readline()) # 컴퓨터의 수
m = int(sys.stdin.readline()) # 연겷할 수 있는 선의 수
parent = [i for i in range(n+1)]
graph = list()
for _ in range(m):
    a, b, c = map(int, sys.stdin.readline().split())
    graph.append([c, a, b])
graph.sort()
res = 0
for node in graph:
    cost, i, j = node
    if find(parent, i) != find(parent, j):  # 서로 부모가 다른 경우
        union(i, j)  # 합침
        res += cost
    #rint(node, parent)
print(res)

 

 

풀이

- 크루스칼(Kruskal) 알고리즘을 활용해 각각의 집합을 연결 시킨다.

- 먼저 조건에 맞게 입력받은 후, 가중치를 기준으로 엣지를 오름차순 정렬한다.

- 그 다음 해당 엣지에 대하여 각 노드를 find()를 활용해 연결한다.(find 후 서로 값이 같은 경우 같은 집합에 포함되기 때문에 스킵)

- 만약 서로 값이 다른 경우 다른 집합이기 때문에 각각의 root를 비교한 후에 최신화한다.(union)

- 이를 반복 후 가중치의 합을 출력한다.

 

 

알게된 점

- union을 실행했을 때 해당 집합의 노드간 root값이 전부 동일해야 한다고 생각했었다.

- 그런데 하나씩 뜯어보니, find함수나 union함수에서 root로 귀결될 것이기 때문에 문제가 없다는 것을 확인했고 문제를 풀 수 있었다.

- find와 parent를 직접 구현하면서 나름 공부할 수 있었던 것 같다.

 

 

참고 사이트

-