Programmers - 섬 연결하기

문제 링크

1. costs를 가격이 낮은 순서부터 차례로 정렬한다.
2. costs를 순서대로 돌면서 다리를 연결하고 component의 개수를 센다.
3. component의 개수가 바뀌지 않았다면 쓸데없는 다리를 지은 것이므로 연결을 취소한다.
4. component의 개수가 1(모든 섬을 연결) 이 될 때 까지 2,3을 반복한다.

def get_component_count(g):
    n = len(g)
    visit = [False for _ in range(n)]

    def dfs(node):
        if visit[node]:
            return
        visit[node] = True
        for next in range(n):
            if next == n:
                continue
            if g[node][next] == 1:
                dfs(next)

    component_count = 0
    for node in range(n):
        if visit[node]:
            continue
        dfs(node)
        component_count += 1

    return component_count


def solution(n, costs):
    g = [[0 for _ in range(n)] for __ in range(n)]
    costs.sort(key=lambda x: x[2])

    total_cost = 0
    before_component_count = n
    for [x, y, cost] in costs:
        total_cost += cost
        g[x][y] = 1
        g[y][x] = 1
        component_count = get_component_count(g)
        if component_count == before_component_count:
            total_cost -= cost
            g[x][y] = 0
            g[y][x] = 0
        if component_count == 1:
            break
        before_component_count = component_count

    return total_cost