프로그래머스 그리디 LV3

섬 연결하기

문제 설명
n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.
다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.

제한사항
섬의 개수 n은 1 이상 100 이하입니다.
costs의 길이는 ((n-1) * n) / 2이하입니다.
임의의 i에 대해, costs[i][0] 와 costs[i][1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i][2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다.
같은 연결은 두 번 주어지지 않습니다. 또한 순서가 바뀌더라도 같은 연결로 봅니다. 즉 0과 1 사이를 연결하는 비용이 주어졌을 때, 1과 0의 비용이 주어지지 않습니다.
모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
연결할 수 없는 섬은 주어지지 않습니다.

입출력 예
n costs return
4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4
입출력 예 설명
costs를 그림으로 표현하면 다음과 같으며, 이때 초록색 경로로 연결하는 것이 가장 적은 비용으로 모두를 통행할 수 있도록 만드는 방법입니다.

과정

def solution(n, costs):
    
    costs.sort(key= lambda x:x[2])
    print(costs)
    success=[]
    answer=0
    for co in costs:
        if not co[0] in success and not co[1] in success:
            success.append(co[0])
            success.append(co[1])
            answer+=co[2]
        
        elif not co[0] in success:
            success.append(co[0])
            answer+=co[2]
        
        elif not co[1] in success:
            success.append(co[1])
            answer+=co[2]

    return answer

제공된 보기리스트를 참고하여 cost값을 바탕으로 오름차순으로 정렬한 후 연결을 했으면 리스트에 넣어주는 식으로 진행하여 마무리 할려고했다.

하지만 5, [[0, 1, 1], [0, 2, 2], [1, 2, 5], [1, 3, 3], [2, 3, 8], [3, 4, 1]] 와같은경우에는 0,1,2 끼리 3,4 끼리만 연결되고 두그룹이 연결되지않아서 4로 반환되는 오류가 발생한다. 정답은 7

코드

def solution(n, costs):
    # kruskal algorithm
    ans = 0
    costs.sort(key = lambda x: x[2]) # cost 기준으로 오름차순 정렬
    connection = [costs[0][0]] 
    while len(connection)!=n:
        for i, cost in enumerate(costs):
            if cost[0] in connection and cost[1] in connection:
                continue
            if cost[0] in connection or cost[1] in connection:
                connection.append(cost[0])
                connection.append(cost[1])
                ans += cost[2]
                connection=list(set(connection))
                costs.pop(i)
                break
    return ans

크루스칼 알고리즘으로 구현하는 듯 하다. 그리디 문제인데 최소신장트리라니... ㅠㅠㅠ

크루스칼 알고리즘 설명
https://chanhuiseok.github.io/posts/algo-33/

[[0,1,1],[3,4,1],[0,2,2],[1,3,3],[1,2,5],[2,3,8]] -> 정렬
connection=[0]
1. [[x],[3,4,1],[0,2,2],[1,3,3],[1,2,5],[2,3,8]]
connection=[0,1]
ans=1
2. [[x],[3,4,1],[x],[1,3,3],[1,2,5],[2,3,8]]
->[3,4,1]연결안됨 패스
connection=[0,1,2]
ans=3
3. [[x],[3,4,1],[x],[x],[1,2,5],[2,3,8]]
connection=[0,1,2,3]
ans=6
4.[[x],[x],[x],[x],[1,2,5],[2,3,8]]
connection=[0,1,2,3,4]
->완료 answer =7