[프로그래머스] 섬 연결하기 문제분석 python

🐒 문제

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

풀이 1

def solution(n, costs):
    answer = 0
    costs.sort(key = lambda x: x[2]) # 
    visited = set([costs[0][0]]) # 
    
    while len(visited) != n:
        for idx, cost in enumerate(costs):
            if cost[0] in visited and cost[1] in visited:  
                continue
            if cost[0] in visited or cost[1] in visited:
                visited.update([cost[0], cost[1]])
                answer += cost[2]
                break
                
    return answer

n = 5
costs = [[0, 1, 1], [2, 4, 1], [2, 3, 1], [3, 4, 1], [0, 4, 5]]

일때

비용 순으로 섬을 나열하고,

첫번째 요소의 섬0을 방문처리한다.
섬0에서 갈 수 있는 섬 부터 확인한다.

섬0 과 섬1은 섬0이 방문되었으니 0 -> 1 로 갈 수 있다. 방문처리하고 비용 1을 증가한다.
//처음으로 돌아간다.

섬0과 섬1은 이미 방문했다.

섬2 와 섬4는 아직 외딴섬이다. 넘어간다.

섬2 와 섬3는 아직 외딴섬이다. 넘어간다.

섬3 과 섬4는 아직 외딴섬이다. 넘어간다.

섬0 과 섬4은 섬0이 방문되었으니 0-> 4로 갈 수있다. 방문처리하고 비용 5를 증가한다.
//처음으로 돌아간다.

섬0과 섬1은 이미 방문했다.

섬2 와 섬4은 섬4가 방문되었으니 0 -> 4 -> 2 로 갈 수 있다. 방문처리하고 비용 1을 증가한다.
//처음으로 돌아간다.

섬0과 섬1은 이미 방문했다.

섬2과 섬4은 이미 방문했다.

섬2 와 섬3는 섬2가 방문되었으니 0 -> 4 -> 2 -> 3 로 갈 수 있다. 방문처리하고 비용 1을 증가한다.

n = 5개의 섬을 모두 방문했으니 종료한다.

비용 8을 리턴한다.

---

풀이 2

def find_parent(parent, a):
    if parent[a] != a:
        parent[a] = find_parent(parent, parent[a])
    return parent[a]

def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent,b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

def solution1(n, costs):
    answer = 0
    parent = [i for i in range(n)]
    costs.sort(key=lambda x:x[2])

    for i in costs:
        if find_parent(parent, i[0]) != find_parent(parent, i[1]):
            union_parent(parent,i[0],i[1])
            answer += i[2]

    return answer

재귀적으로 부모 노드를 찾아내서 부모가 같은 노드면 연결하지 않음

---