섬 연결하기
def ancestor(node, parents):
if parents[node] == -1:
return node
else:
return ancestor(parents[node], parents)
def solution(n, costs):
answer = 0
costs.sort(key = lambda x : x[2])
parents = [-1]*n
bridges = 0
while bridges < n-1 :
v1, v2, cost = costs.pop(0)
if (next_v1 := ancestor(v1, parents)) != ancestor(v2, parents):
answer += cost
parents[next_v1] = v2
bridges += 1
return answer
크루스칼 알고리즘
직접짠 코드는 아니지만 어떻게 이런생각을 하는지 대단한듯. 크루스칼 알고리즘 모른다면 공부부터 하고 오셈. 나도 크루스칼 알고리즘을 잘 몰라서 원래 저런식으로 union-find 알고리즘을 검사하는게 맞나? 싶은데, 이 코드는 단방향 그래프로 union-find 알고리즘을 구현했다.
links는index의 부모가 없으면-1있으면 해당 부모의index를 가지게하고cycle검사를DFS? 처럼 타고타고 올라가게 구현했음
내가 알기로 cycle이 있는지를 판별하는 union-find 알고리즘은 집합을 이용하는데, 이코드는
cur_node의 최고 조상의 부모 =cur_node와 연결된 노드
이렇게 판별하니… 신기하다.
def ancestor(node, parents):
if parents[node] == -1: # 부모가 없는 상태
return node
else:
return ancestor(parents[node], parents)
def solution(n, costs):
answer = 0
costs.sort(key = lambda x : x[2])
parents = [-1]*n
bridges = 0
while bridges < n-1 :
v1, v2, cost = costs.pop(0)
if (next_v1 := ancestor(v1, parents)) != ancestor(v2, parents): # 부모가 다르면 no cycle
answer += cost
parents[next_v1] = v2 # v1의 최고 조상이 v2를 가리킴
bridges += 1
return answer