[ 백준 1647 ] 도시 분할 계획 - Python

문제 보기

이 문제는 최소 신장 트리(Minimum Spanning Tree) 문제이다.

 

두 마을로 분리하기 위해서 먼저 최소 신장 트리를 구현하고, 최소 신장 트리를 구성하는 간선 중에 비용이 가장 높은 간선을 제거하였다.

 

위 과정을 구현하기 위해서 크루스칼 알고리즘을 사용하였다.

1. 입력 받은 간선을 비용을 기준으로 내림차순 정렬을 한다.

2. 비용이 낮은 간선부터 사이클 여부를 확인하고 사이클이 발생하지 않으면 삽입한다.

3. 모든 간선에 대해서 위 과정을 수행한 후 제일 마지막에 삽입한 간선을 제거하였다.

코드

def find_parent(x):
    if parent[x] != x:
        parent[x] = find_parent(parent[x])
    return parent[x]


def union_parent(a, b):
    a = find_parent(a)
    b = find_parent(b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b


if __name__ == "__main__":
    n, m = map(int, input().split())  # 집의 개수, 길의 개수 입력받기
    graph = []
    for _ in range(m):  # 길 입력받기
        a, b, c = map(int, input().split())
        graph.append([c, a, b])

    parent = [0] * (n + 1)
    for i in range(1, n + 1):
        parent[i] = i

    # 간선 정렬
    graph.sort()

    # 크루스칼 수행
    selected = []  # 선택된 간선

    answer = 0
    for c, a, b in graph:
        if find_parent(a) != find_parent(b):
            union_parent(a, b)
            answer += c
            selected.append(c)

    # 마을을 두개로 분리하기 위해서 마지막 간선 제거
    answer -= selected.pop()

    # 출력
    print(answer)