[Programmers] 그리디 - 섬 연결하기

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

프로그래머스

 

 

첫 번째 시도

각 노드를 하나씩 탐방하면서 아직 방문하지 않고, 비용이 가장 적은 노드를 연결하는 방식으로 했다. -> 실패

 

정답 참고

https://velog.io/@henrynoowah/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%84%AC-%EC%97%B0%EA%B2%B0%ED%95%98%EA%B8%B0-PYTHON

[프로그래머스] 섬 연결하기 - PYTHON

이 문제는 Kruskal 알고리즘을 이용해서 푸는 문제이다.

Kruskal 알고리즘이란?

탐욕적인 방법을 이용하여 네트워크의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 것

+) 탐욕적인 방법

- 결정을 해야 할 때마다 그 순간에 가장 좋다고 생각되는 것을 선택함으로써 최종적인 해답에 도달하는 것

- 탐욕적인 방법은 그 순간에는 최적이지만, 전체적인 관점에서 최적인라는 보장이 없기 떄문에 반드시 검증을 해야 함

- Kruskal 알고리즘은 최적의 해답을 주는 것으로 증명되어 있음 !

 

Kruskal 알고리즘의 동작

1. 그래프의 간선들은 가중치의 오름차순으로 정렬

2. 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택

 - 즉, 가장 낮은 가중치를 먼저 선택

 - 사이클을 형성하는 간선을 제외

3. 해당 간선을 현재의 MST(최소 비용 신장 트리)의 집합에 추가

 

풀이

def solution(n, costs):
    answer = 0
    costs.sort(key=lambda x:x[2]) # 가격 기준 오름차순 정렬
    link = set([costs[0][0]])
    
    while len(link) < n:
        for node1, node2, cost in costs:
            if node1 in link and node2 in link: # 둘 다 이미 연결되어 있다면
                continue
            if node1 in link or node2 in link: # 둘 중 하나는 연결되어 있지 않고 하나는 연결되어 있다면
                link.update([node1], [node2])
                answer += cost
                break
    return answer

 

먼저 비용을 기준으로 오름차순 정렬 한 후

가장 비용이 적은 것의 첫 번째 노드를 link에 넣는다.

이후 하나씩 체크하면서 link에 들어있는 것과 들어있지 않은 것이 연결되어있으면 해당 노드를 연결한다.

 

배운 점

Kruskal 알고리즘만 알고 있었다면 쉽게 풀었을 것 같다. 최대한 문제를 많이 풀어보자!

 

set 자료형에 대한 문법도 새로 익혔다.

A = set([1, 2, 3]) # 이렇게 숫자 값을 넣을 때 대괄호를 사용해야 한다.

B = set('abc')
print(B)
>>> set(['a', 'b', 'c'])

# set 자료형은 인덱싱이 불가능하다.

A & B # 집합 자료형의 교집합 (방법1)
A.intersection(B) # 집합 자료형의 교집합 (방법2)

A | B # 집합 자료형의 합집합 (방법1)
A.union(B) # 집합 자료형의 합집합 (방법2)

A - B # 차집합
A.difference(B) # 차집합

A = set(['a', 1, 4, 'c'])
A.remove(1) # remove 함수를 통해 빼고싶은 인자로 값 삭제 가능

A.add('b') # add는 하나의 원소를 추가
A.update([0, 9]) # update 는 여러 개의 원소를 추가