백준 / 최소 스패닝 트리 / 1197번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 최소 스패닝 트리 / 1197번 (골드 4단계)

문제 사이트: https://www.acmicpc.net/problem/1197

 

문제 설명

---

나의 풀이

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline


# 유니온 파인드용 함수
def find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x])  # 경로 압축
    return parent[x]


def union(parent, a, b):
    root_a = find(parent, a)
    root_b = find(parent, b)
    if root_a != root_b:
        parent[root_b] = root_a  # 한 쪽으로 합침


def main():
    V, E = map(int, input().split())
    edges = []

    for _ in range(E):
        a, b, cost = map(int, input().split())
        edges.append((cost, a, b))

    # 가중치 기준으로 정렬
    edges.sort()

    # 각 노드의 부모를 자기 자신으로 초기화
    parent = [i for i in range(V + 1)]

    mst_weight = 0
    for cost, a, b in edges:
        if find(parent, a) != find(parent, b):
            union(parent, a, b)
            mst_weight += cost

    print(mst_weight)


if __name__ == "__main__":
    main()

---

※ 알아야 할 것

import heapq


def dijkstra(graph, n, start):
    distances = [float('inf')] * (n + 1)
    distances[start] = 0
    pq = [(0, start)]
    visited = [False] * (n + 1)

    while pq:
        dist, node = heapq.heappop(pq)
        if visited[node]:  # 이미 방문한 노드인 경우 재 방문을 하지 않는다.
            continue
        visited[node] = True  # 현재 방문한 노드는 방문했다는 것을 처리한다.

        # 다음 노드 탐색
        for next_node, weight in graph[node]:
            if not visited[next_node]:  # 연결된 노드가 방문하지 않았을 경우
                new_dist = dist + weight  # 자신 + 다음 가중치 값
                if new_dist < distances[next_node]:
                    distances[next_node] = new_dist
                    heapq.heappush(pq, (new_dist, next_node))

    return sum(distances[1:])

다익스트라 문제로 이해를 하고 1번부터 n번까지 탐색하는 방법은 시간이 너무 오래 걸려서 풀지 못했습니다!