1197번 - 최소 스패닝 트리
def union(x, y):
x, y = find(x), find(y)
if x > y :
parent[x] = y
else:
parent[y] = x
위의 x, y 들은 왜 비교해야되는건가요??
x, y는 가중치가 아니고 그냥 정점 아닌가요?
전체 코드가 없지만 아마 진짜 그냥 정점 인덱스끼리 비교 같습니다. 정점 인덱스 순으로는 비교하지 않아도 될 뿐만 아니라 오히려 저렇게 비교하면 한쪽으로 쏠려 더 불리합니다.
x를 루트로 하는 트리의 높이나 트리의 크기를 비교하고 큰 쪽에 작은 쪽을 합치는 것이 좋습니다.
위 코드에서 뭐가 문제일까요? 정답 코드와 비교해봐도 잘 모르겠습니다.
아 해결했습니다. 입력을 바보같이 잘못받았네요 감사합니다 !
댓글을 작성하려면 로그인해야 합니다.
acg6138 1년 전
def union(x, y):
x, y = find(x), find(y)
if x > y :
parent[x] = y
else:
parent[y] = x
위의 x, y 들은 왜 비교해야되는건가요??
x, y는 가중치가 아니고 그냥 정점 아닌가요?