섬 연결하기 with 파이썬

• Kruskal 알고리즘

탐욕적인 방법을 이용해서 그래프의 모든 정점을 최소 비용으로 연결하는 방법

처음 시작하는 노드로 부터 하나의 간선을 선택해 간다.

# 최소 비용으로 모든 섬 통행
# A -> B -> C
# 오류


def solution(n, costs):
    total = 0
    island = set()
    roots = []
    costs = sorted(costs, key=lambda x: -x[2])

    # 경로 리스트
    while len(island) < n:
        r1, r2, c = costs.pop()
        if r1 in island and r2 in island:
            continue
        island.add(r1)
        island.add(r2)
        roots.append((r1,r2,c))

    return total

# 방문 리스트 활용해서 다시 방문하는 것 체크

def solution(n, costs):
    answer = 0
    costs.sort(key=lambda x: x[2])
    visited = [0] * n
    visited[0] = 1

    while sum(visited) != n:
        for cost in costs:
            i1, i2, c = cost
            if visited[i1] or visited[i2]:
                if visited[i1] and visited[i2]:
                    continue
                else:
                    visited[i1] = 1
                    visited[i2] = 1
                    answer += c
                    break
    return answer