파이썬 백준 1197 최소 스패닝 트리

import sys input = sys.stdin.readline Vn, En = map(int, input().split()) V = {} E = [] for i in range(1, Vn + 1) :     V[i] = i for i in range(En) :     E.append(list(map(int, input().split()))) E.sort(key = lambda x : x[2]) def endof(x) :     if V[x] == x :         return x     return endof(V[x]) def check(a, b) :     if endof(a) == endof(b) :         return True     return False def connect(a, b) :     if endof(a) < endof(b) :         V[endof(a)] = endof(b)     else :         V[endof(b)] = endof(a) cost = 0 for v1, v2, c in E :     if not check(v1, v2) :         connect(v1, v2)         cost = cost + c print(cost)

최소 길이 부분그래프를 찾는데, 선마다 코스트가 있어서 그중 비용이 최소인 것을 찾는 문제이다.

 

선으로 이어진 두 점은 하나의 점과 위상이 같다. 즉, 두 점을 선으로 있는 것은 이루는 두 점을 하나로 합치는 과정인 셈이다. 

그리고 이미 연결된 두 점을 다시 이으면 사이클이 생기고, 사이클은 최소 길이 부분그래프가 될 수 없다. (사이클에서 선 하나 뗀게 사이클보다 짧기 때문)

즉, 연결되지 않은 두 점은 선으로 잇고, 이미 연결된 두 점이라면 그 사이의 선은 버린다. 이를 모든 선에 대해 반복하면 최소 길이 부분그래프 중 하나를 구할 수 있다.

 

선을 구성하는 두 점이 이미 연결되었는지를 판별하기 위해서 트리 구조를 이용했다.

선을 연결할 때마다 두 점을 트리의 부모자식 관계로 만들어준다.

그렇다면 이미 연결된 두 점이라면, 각각 트리를 따라 올라갔을 때 root가 같을 것이다. 다르다면 연결되지 않은 것이니 이어준다. 이때 우선순위가 유지되어야 하니 둘을 직접 붙이는 것이 아니라 둘의 루트끼리 우선순위를 유지하는 방향으로 이어줘야 한다.

 

최소 길이 부분그래프는 둘 이상 존재할 수 있고, 그중 어떤 것을 구할지는 선을 어떤 순서로 잇냐에 따라 결정된다. 즉, 선들을 코스트가 낮은 순서대로 정렬한 뒤 위의 과정을 거치면 최소 코스트의 최소 길이 부분그래프를 찾을 수 있다.