[알고리즘] 탐욕법(Greedy) 프로그래머스 3단계 - 섬 연결하기

최소 신장 트리 (MST)

그래프에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결하는 것

• 간선의 가중치의 합이 최소
• 사이클 포함 X

Kruskal MST

탐욕적인 방법(그리디)을 이용하여 모든 정점을 최소 비용으로 연결

1. 그래프의 간선들을 오름차순으로 정렬
2. 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선 선택
3. 해당 간선을 현재의 집합에 추가 (union-find 알고리즘)
 ex) [{1}, {2}] ⇨ 간선 (3,4) 추가 ⇨ [{1}, {2}, {3}, {4}] 
 ⇨ 간선 (2, 5) 추가 ⇨ [{1}, {2, 5}, {3}, {4}] ⇨ 간선 (1, 2) 추가 
 ⇨ [{1, 2, 5}, {3}, {4}]

https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html

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

    for i in range(n):
        bridge.append({i})
    
    for i in costs:
        temp1 = set()
        temp2 = set()
        for j in bridge:
            if i[0] in j:
                temp1 = j
            if i[1] in j:
                temp2 = j
        if temp1 == temp2:
            continue
        else:
            bridge.remove(temp1)
            bridge.remove(temp2)
            bridge.append(temp1|temp2)
            answer += i[2]
            if len(bridge) == 1:
                break

    return answer

풀이과정

ex) costs = [[0,1,1], [1,3,1], [0,2,2], [1,2,5], [2,3,8]]

1. 비용을 기준으로 costs를 오름차순 정렬한다.

2. 섬의 개수 만큼 집합을 만들어준다. [{0}, {1}, {2}, {3}]

3. 사이클이 형성되지 않도록 간선을 선택한다.

• temp1과 temp2 집합을 만든다.
• 만든 bridge for문을 돌며, 각 원소가 집합 안에 들어있는지 확인한다.
• 서로 다른 집합 안에 있으면, 합쳐준다.
• 집합의 개수가 1개가 되면, 반복문을 빠져나온다.

새로 배운 내용

set(집합) 만들기

집합은 중복이 허용되지 않으며, 순서도 없다.

s1 = {1, 2, 3, 4}
s2 = set([1, 3])	// {1, 3}
s3 = set()		// 비어있는 집합 자료형
s4 = set("hello")	// {'h', 'e', 'l', 'o'}

set(집합) 합집합, 교집합, 차집합

s1 = set([1, 2, 3, 4, 5])
s2 = set([3, 4, 5, 6, 7])

1. 합집합

s1.union(s2)
s1 | s2

{1, 2, 3, 4, 5, 6, 7}

2. 교집합

s1.intersection(s2)
s1 & s2

{3, 4, 5}

3. 차집합

s1.difference(s2)
s1 - s2

{1, 2}