https://www.acmicpc.net/problem/1922
시간 2초, 메모리 256MB
input :
- N (1 ≤ N ≤ 1000)
- M (1 ≤ M ≤ 100,000)
- a b c 가 주어져 있다고 하면 a컴퓨터와 b컴퓨터를 연결하는데 비용이 c (1 ≤ c ≤ 10,000)
든다는 것을 의미한다. a와 b는 같을 수도 있다.
output :
- 모든 컴퓨터를 연결하는데 필요한 최소비용을 첫째 줄에 출력
조건 :
- 모든 컴퓨터를 연결하는데 필요한 최소비용을 출력하라.
- 모든 컴퓨터를 연결할 수 없는 경우는 없다.
뭔가 과거에 별표를 해 뒀던 문제인데. 크루스칼 알고리즘을 공부하고나서 풀어봐야지 하고 해둔것 같다.
문제를 처음에 보고 예제를 확인하니 최소 스패닝 트리를 뜻하는 건가 싶었다. 그러다가 예제를 다시 보니 어 그냥 각 정점에서 가장 짧은 거를 연결하는 건가? 하는 생각이 들어 그림을 그리다가 루프, 사이클이 존재하면 안 되는 것을 보고 아 처음이 맞다.
하는 생각으로 코드를 짜기 시작했다.
일단 모든 간선들을 입력 받은 후 이를 cost가 가장 짧은 것부터 연결 시켜준다.
이 때 사이클, 루프를 판단해야 하므로 필요한 것이 각 정점의 root 가 무엇인지 찾아야 하고 각 정점들이 연결될 때 이를 업데이트 해줘야 한다.
root를 찾기 위해 find_parent 함수를 만들어 주자.
이 함수의 경우 각 정점의 root를 리턴 해줘야 하는데, 맨 처음 parent 배열을 초기화 할 때 각 정점의 root 는 자기자신이다.
그렇기에 parent[x] == x 일 때만 root인 것이다.
그렇지 않은 경우라면 dp를 풀 때의 테크닉을 이용해
parent[x] = find_parent(parent[x]) 로 값을 업데이트 하자.
자기 자신이 root가 아니니까 재귀를 통해 더 들어가서 끄집어 와야 한다.
그러고 return parent[x] 해주자.
def find_parent(x):
if parent[x] != x:
parent[x] = find_parent(parent[x])
return parent[x]부모를 찾았다면 인제 작은 놈으로 합쳐서 연결되었음을 나타내자.
연결하려는 두 정점의 부모들을 가지고 더 작은 놈을 기준으로 합치는 것이다.
이 때, 주의 할 것은
우리가 x, y를 union 하는 것이지만 얘네들의 root는 x, y가 아닐 수도 있다. 그렇기에 root_x, root_y에다가 각각의 부모를 가지고 온 후,
이 둘을 비교해서 합쳐 주자.
def union(x, y):
root_x = find_parent(x)
root_y = find_parent(y)
if root_y > root_x:
parent[root_y] = root_x
else:
parent[root_x] = root_yimport sys
from heapq import heappop, heappush
def find_parent(x):
if parent[x] != x:
parent[x] = find_parent(parent[x])
return parent[x]
def union(x, y):
root_x = find_parent(x)
root_y = find_parent(y)
if root_y > root_x:
parent[root_y] = root_x
else:
parent[root_x] = root_y
n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
edge = []
parent = [i for i in range(n + 1)]
ans = 0
for i in range(m):
a, b, c = map(int, sys.stdin.readline().split())
heappush(edge, (c, a, b))
for i in range(m):
cost, a, b = heappop(edge)
if find_parent(a) != find_parent(b):
union(a, b)
ans += cost
print(ans)오랜만에 복습 잘 하고 갑니다.
