Written by 최태열
on November 24, 2020

[Python][프로그래머스][Level3] 섬 연결하기

코드

def check(start,ck,board):
    ck[start]=1
    for idx, end in enumerate(board[start]):
        if end==0 or ck[idx]==1:
            continue
        check(idx,ck,board)
    return ck

def solution(n, costs):
    answer=0
    board=[[0]*n for _ in range(n)]
    for start,end,cost in sorted(costs,key=lambda x: x[2]):
        ck=check(start,[0]*n,board)
        if sum(ck)==n:
            return answer
        if ck[end]==1:
            continue
        answer+=cost
        board[start][end]=1
        board[end][start]=1
    return answer

kruskal 알고리즘은 최소 비용으로 다리 연결하기 같은 문제에 자주 쓰이는데,

가장 적은 비용의 다리를 건설하다 보면 전체를 잇는 다리가 모두 완성되고 그때의 비용이 최솟값이다 라는 내용이다.

이 문제가 딱 그러하다.

적은 비용의 다리부터 짓는 거는 쉽지만 언제까지 지어야하고 어떤 다리는 짓지 말아야하는 지가 제일 중요하다.

한 지점에서 이동 가능한 모든 다리를 check 배열에 1로 만든다.

만약 check 배열의 합이 n 이라면 다리가 모두 연결된 것이고

check[end]가 1이라면 두 다리는 이미 연결된 것이기 때문에 지을 필요가 없다.

Discussion and feedback

← → Top