BOJ 14950 - 정복자

문제

백준 온라인 저지 - 1번

풀이 과정

모든 정점을 잇는 최단 경로를 찾는 문제입니다.
즉, 최소 스패닝 트리를 구현하면 되기 때문에 크루스칼 알고리즘 을 활용해서 문제를 해결했습니다.
다만 각 경로를 선택할때마다 모든 간선의 비용이 증가하기 때문에 t * 이전까지 선택된 간선의 개수 만큼 추가적인 값을 누적해줍니다.

코드

import sys


def union(u, v):
    pv, pu = find(u), find(v)

    if pv != pu:
        if rank[pv] > rank[pu]:
            parent[pu] = pv
        else:
            if rank[pv] == rank[pu]:
                rank[pu] += 1

            parent[pv] = pu


def find(u):
    if parent[u] == u:
        return u

    parent[u] = find(parent[u])

    return parent[u]


def solution():
    acc = 0
    found = 0

    roads.sort(key=lambda r: r[2])

    for frm, to, cost in roads:
        if find(frm) != find(to):
            union(frm, to)
            acc += (cost + found * t)
            found += 1

            if found == N - 1:
                break

    return acc


if __name__ == '__main__':
    N, M, t = list(map(int, sys.stdin.readline().split()))
    roads = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]

    parent = [v for v in range(N + 1)]
    rank = [0] * (N + 1)

    answer = solution()
    print(answer)