문제

입력 , 출력

solution

import sys

input = sys.stdin.readline


def find(a):
    if a == parent[a]:  # 자신이 루트노드면 자신을 반환
        return a
    parent[a] = find(parent[a])  # 루트노드를 찾음
    # 메모이제이션과 비슷한 아이디어
    # a의 부모를 find(parent[a])로 바꿔줌
    return parent[a]


def union(a, b):
    a = find(a)
    b = find(b)
    # a , b의 루트노드를 찾아줌
    if b < a:
        parent[a] = b
    else:
        parent[b] = a


n = int(input())
m = int(input())
arr = []
parent = [i for i in range(n + 1)]
res = 0
for i in range(m):
    a, b, c = map(int, input().split())
    arr.append((
        c,
        a,
        b,
    ))

arr.sort(key=lambda x: x[0])
for dis, a, b in arr:
    if find(a) != find(b):  # 루트가 같으면 할 필요가 없음
        union(a, b)
        res += dis
print(res)

설명

최소스패닝 트리를 구현만 하면 풀리는 문제이다
처음에 parent 배열을 만든 뒤에 자기 자신을 조상으로 만든다.
그리고 (a,b) = 연결된 노드 , c = 간선의 가중치
간선의 가중치를 기준으로 입력받은 배열로 정렬해준다.

최소 스패닝트리

사이클 없이 최소한의 가중치로 연결을 하는 것 이다.
find로 루트 노드를 찾는다
find 함수에서 자신이 루트노드 일 경우에는 자신을 return해준다
union 함수에서 받은 간선 두개의 루트 노드를 뽑아준다
처음 union에 들어가기 전에 find로 루트노드를 먼저 찾아서
같지 않다면 연결을 해준다
여기서는 노드 (a,b) 중에 노드 번호가 작은것을 루트노드로 지정을 해준다.
여기서 배열을 가중치를 기준으로 정렬을 했기 때문에 최소한의 가중치로 연결이 된다.
그래서 연결에 성공하면 res에 가중치를 계속 더해주면
결과값이 나온다.