프로그래머스 섬 연결하기 (파이썬), 최소 신장 트리, 크루스칼

문제: https://programmers.co.kr/learn/courses/30/lessons/42861?language=python3# 

코딩테스트 연습 - 섬 연결하기

첫번째 제출 코드 (오답)

import heapq as hq


def solution(n, costs):
    answer = 0
    visited = set()
    q = []
    SUM = 0
    costs.sort(key=lambda x: (x[2], x[0], x[1]))
    
    for start, end, cost in costs:
        if start in visited and end in visited:
            continue
            
        answer += cost
        visited.add(start)
        visited.add(end)
        if len(visited) == n:
            break
    print(visited)
        
    return answer

# solution(4, [[0,2,2], [0,1,1],[1,2,5],[1,3,1],[2,3,8]])

단순하게 costs 배열을 비용이 짧은 것을 우선으로 하여 정렬을 한 뒤 visited 라는 배열 안에 두 섬의 쌍이 동시에 존재하지 않을 경우 visted에 넣고 answer에 비용을 더하여 출력하였습니다.

하지만 정답이 아니었고 답이 생각나질 않아 검색을 해본 결과 크루스칼이라는 알고리즘으로 풀어야 한다고 하여 다시 제출하였습니다.

 

두번째 제출 코드 (정답)

import heapq as hq
def solution(n, costs):
    answer = 0
    visited = set([costs[0][0]])
    costs.sort(key=lambda x: (x[2], x[0], x[1]))
    
    while len(visited) < n:
        for start, end, cost in costs:
            if start in visited and end in visited:
                continue
            if start in visited or end in visited:
                answer += cost
                visited.update([start, end])
                break
    return answer

위 코드를 뜯어보겠습니다.

 

visited = set([costs[0][0]])

먼저 시작점을 visited 에 넣어 방문 처리를 합니다. 자기자신으로 가는 비용은 0이니 따로 answer 를 더하지 않습니다.

 

while len(visited) < n:

visited가 모든 경로를 방문 할 때 까지 반복합니다.

 

for start, end, cost in costs:

먼저, 가장 경로가 간선의 정보를 처리니다.

 

if start in visited and end in visited:
    continue

만약 지금 처리하는 연결된 두 섬이 이미 앞에서 처리되어 연결되어 있다면 무시합니다.

 

if start in visited or end in visited:
    answer += cost
    visited.update([start, end])
    break

지금 처리하는 간선의 두 노드 중 하나만 처리되었다면 다른 하나를 추가합니다.

set이라서 중복된 노드는 알아서 제외됩니다.

그 후 cost를 계속 반복하는 것이 아니라 처음으로 돌아가 다시 비용이 짧은 간선부터 시작합니다.

 

 

크루스칼 알고리즘 

간선의 개수 : E, 

가장 많은 시간이 소요되는 곳은 정렬을 수행하는 부분

시간 복잡도 : O(ElogE)

 

신장트리 : 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프

최소 신장 트리: 최소한의 비용으로 구성되는 신장 트리

 

크루스칼은 최소 신장 트리의 알고리즘으로 그리디 알고리즘을 사용합니다.

크루스칼 동작 과정

1. 간선 데이터를 비용에 따라 오름차순 정렬
2. 간선을 하나씩 확인 > 현재 간선이 싸이클을 발생하는지 확인

   1) 사이클을 발생하지 않는 경우 최소 신장 트리에 포함

   2) 사이클이 발생하는 경우 포함 X

3. 모든 간선에 대해 2번 반복