[프로그래머스][그리디] 섬 연결하기

def getParent(idx):#제일 부모를 반환
    if idx==parent[idx]:
        return idx
    else :return getParent(parent[idx])
        
def union(f,s):
    f=getParent(f)
    s=getParent(s)
    if f<s:
        parent[s]=getParent(f)#최상위 부모로 지정해줘야함***
    else :
        parent[f]=getParent(s)
def solution(n, costs):
    answer = 0
    global parent#초기의 부모는 자기 자신
    parent=[i for i in range(n)]#초기의 부모는 자기 자신
    #cost기준으로 정렬
    sorted_costs=sorted(costs,key= lambda x : x[2])
    for i in sorted_costs:
    #cost작은거부터 조회하면서 간선 연결 (parent를 union)
  #      print(i[0], getParent(i[0]), i[1],getParent(i[1]))
        if getParent(i[0])!=getParent(i[1]):#(사이클이 없을 때) parent[i[0]]!=parent[i[1]]로 조회하면 안됨
            union(i[0], i[1])
            answer+=i[2]
    print(parent)
    #연결할 때 cycle 이 있는지 확인해야함    
    
    return answer

 

최소 신장트리를 만들면 되는 문제이다.
(크루스칼 알고리즘)

 

헷갈렸던것
1. union함수에서 지금 연결하는 노드의 부모만 갱신해주면 안됨!
-> 지금 연결하는 노드가 다른것과도 연결되어있을 수 있으므로, 지금 연결하려는 노드의 제일 상위 부모를 찾아 부모의 부모를 갱신해줘야함
2. 사이클이 있는지 확인할 때 : parent 배열(부모배열)만 조회하면 될 것이라고 생각했으나 ㄴㄴ
-> 1번과정에 의해 갱신될 때 제일 상위의 부모의 부모만 바뀌게 되므로 사이에 있던 parent 배열만 보면 사이에있는 노드들은 부모의 부모가 생겼으나 그 사실을 모른채 자신의 부모를 parent 배열에 담고있음. 즉, parent 배열이 최상위 부모를 뜻하는 것은 아님. 따라서 getparent 함수를 통해서 최상위 부모를 가져와야함. 
그게 아니면 parent 배열을 만들 때 최상위 부모를 적재하자...