[그리드] 섬 연결하기 (python)

문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/42861

프로그래머스

문제 풀이

• 시작 노드가 주어지지 않는 채, 연결 정보들이 주어졌을 때의 모든 노드를 탐색 하는 최소 가중치(비용)를 구하는 문제
• 모든 노드를 탐색하면서 최소 가중치를 구하는 알고리즘을 짜야함. 이 때 크루스칼 알고리즘 떠올리는 짬이 있어야함
• 크루스칼은 주어진 정보들을 가중치를 기준으로 오름차순으로 정렬한 뒤, 하나하나 간선들을 이어나가는 과정
• 이 때, 특정 경로에서 하나의 왕복 루틴이 완성 되어버리면 그 경로만 반복되고 무한 루틴이 발생. 
• 왕복 루틴을 체크하는 것은 탐색 중인 현재 노드들의 부모 노드(제일 첫)를 확인하면 됨.
• 부모 노드가 같으면 이어졌을 때 왕복이 되므로 해당 탐색은 continue
• 다르면 이제 부모 노드 정보를 업데이트 해줘야 하는데 특별한 조건이 있지 않은 한 최소 번호가 부모가 되도록 통일
• 이 부모 노드 업데이트는 현재 탐색 노드에 대해 정보를 입히는게 아니라 제일 끝 부모 노드의 정보를 업데이트 해주는 것
• costs 전체 정보를 탐색하기 전에 탐방이 끝날 수 있으므로 그 조건은 num이라는 카운트를 만들어 체크

소스 코드

def findParent(cur,par):
    if par[cur]==cur:
        return cur
    return findParent(par[cur],par)

def solution(n, costs):
    answer= 0
    costs.sort(key=lambda x:x[2])
    parent = [i for i in range(n)]
    num = 0		# costs를 다 순회하기 이전에 탐색 다 끝났다면 종료하기 위한 장치
    for cost in costs:
        s,e,c = cost    
        S = findParent(s,parent)	#findeParent
        E = findParent(e,parent)
        if (S==E):		#compareParent
            continue
        else:
            if(S<E):	#unionParent
                parent[E]=S
            else:
                parent[S]=E
            answer+=c
            num+=1	
        if(num==(n-1)):	#모든 노드를 다 탐방한 것이므로 종료
            break
            
    return answer

print(solution(4,[[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]))