[python 파이썬] [프로그래머스] 섬 연결하기(탐욕법)

https://programmers.co.kr/learn/courses/30/lessons/42861

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

문제 설명

n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.

다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.

제한사항

• 섬의 개수 n은 1 이상 100 이하입니다.
• costs의 길이는 ((n-1) * n) / 2이하입니다.
• 임의의 i에 대해, costs[i][0] 와 costs[i] [1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i] [2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다.
• 같은 연결은 두 번 주어지지 않습니다. 또한 순서가 바뀌더라도 같은 연결로 봅니다. 즉 0과 1 사이를 연결하는 비용이 주어졌을 때, 1과 0의 비용이 주어지지 않습니다.
• 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
• 연결할 수 없는 섬은 주어지지 않습니다.

입출력 예

ncostsreturn

4

[[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]

4

입출력 예 설명

costs를 그림으로 표현하면 다음과 같으며, 이때 초록색 경로로 연결하는 것이 가장 적은 비용으로 모두를 통행할 수 있도록 만드는 방법입니다.

---

◆ 문제 풀이

- 이번 문제는 크루시칼 알고리즘을 사용해서 푼다

▶ Kruskal 알고리즘 이란?

- 탐욕적인 방법(greedy method) 을 이용하여 가중치를 간선에 할당한 그래프(네트워크)의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 것

- 탐욕적인 방법이란?
결정 할 때마다 그 순간에 가장 좋다고 생각되는 것을 선택하며 최적의 해답에 도달하는 것
탐욕적인 방법은 그 순간에는 최적이지만, 전체적인 관점에서 최적이라는 보장이 없기 때문에 반드시 검증해야 한다.

- Kruskal 알고리즘은 최적의 해답을 주는 것으로 증명되어 있으며 아래 두 조건을 만족해야한다

1) 최소 비용 신장 트리(MST)가 최소 비용의 간선으로 구성되었는가
2) 사이클을 포함하지 않음 의 조건에 근거하여 각 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택 한다. 

 

▶ Kruskal 알고리즘의 구현

1) 그래프의 간선들을 가중치를 기준으로 오름차순으로 정렬한다.
2) 정렬된 리스트에서 사이클이 발생하지 않도록 간선을 선택한다. 
- 즉, 가장 낮은 가중치를 먼저 선택함과 동시에 사이클을 형성하는 간선을 제외한다.
3) 해당 간선을 현재의 최소 비용 신장 트리(MST)의 집합에 추가한다.

 

▶사이클의 방지

 

 

def solution(n, costs):
    answer = 0
    bridge = 0
    cycle = {k:k for k in range(n)}  #cycle 도는것을 방지하기 위해 만듦
    costs.sort(key=lambda x : x[2]) #cost를 오름차순으로 정렬
    for i in costs:
        if i[0] > i[1]: #i[0]이 #i[1]보다 큰 경우 바꿔줌
            i[0], i[1] = i[1], i[0]
        if cycle[i[1]] == cycle[i[0]]: #cycle의 value가 같으면 이미 연결되었다는 것임
            continue
        answer += i[2]
        bridge += 1 
        past = cycle[i[1]] #i[1]을 i[0]의 value값으로 바꾸기 전에 저장 -> i[1]과 같은 value값을 가지고 있는 것도 바꿔줘야하기 때문
        cycle[i[1]] = cycle[i[0]] #나보다 작은 숫자의 섬으로 cycle의 value를 바꿔줌
        for k, v in cycle.items(): #만약 0-1-2, 3-4처럼 고립된상태에서 2-3이 연결되면 4의 value도 바꿔주어야함
            if v==past:
                cycle[k]=cycle[i[0]]
        if bridge == n-1:
            break
    return answer