[Programmers] 섬 연결하기
1. 문제 설명
n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.
다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.
2. 제한 사항 및 입출력 예시
2.1 제한 사항
- 섬의 개수 n은 1 이상 100 이하입니다.
- costs의 길이는
((n-1) * n) / 2
이하입니다. - 임의의 i에 대해, costs[i][0] 와 costs[i][1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i][2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다.
- 같은 연결은 두 번 주어지지 않습니다. 또한 순서가 바뀌더라도 같은 연결로 봅니다. 즉 0과 1 사이를 연결하는 비용이 주어졌을 때, 1과 0의 비용이 주어지지 않습니다.
- 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
- 연결할 수 없는 섬은 주어지지 않습니다.
2.2 입출력 예
n | costs | return |
---|---|---|
4 | [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] | 4 |
2.3 입출력 예 설명
costs를 그림으로 표현하면 다음과 같으며, 이때 초록색 경로로 연결하는 것이 가장 적은 비용으로 모두를 통행할 수 있도록 만드는 방법입니다.
3. 해설
이 문제를 확실하게 이해하기 위해서는 신장 트리라는 개념이 필요하다.
- 신장 트리(Spanning Tree) : 그래프 내의 모든 정점을 포함하는 트리
- 최소 비용 신장 트리(Minimum Spanning Tree) : 신장 트리에 사용된 간선들의 가중치 합이 최소인 신장 트리
이 문제의 요구사항은 MST를 구해서, 그 간선들의 가중치 합을 구하라는 것이다. 이때 사용하는 알고리즘은 크루스칼/프림 알고리즘이 있는데, 간단히 설명하자면,
- 크루스칼 알고리즘 : 신장 트리가 생성될 때 까지 가중치가 작은 간선들을 골라나간다. 이때 Cycle이 없어야 한다.
- 프림 알고리즘 : 특정 정점에서 시작하여 정점에 연결된 간선들 중 가중치가 작은 것을 선택해나간다. 이때 Cycle이 없어야 하는건 크루스칼과 같다.
여기서는 좀 더 직관적인 방법인 크루스칼을 사용하면 문제가 해결된다.
-
costs
배열을 가중치가 작은 순서대로 정렬한다. -
방문한 노드들을 저장할 집합을 생성한다. (집합은 중복이 허용되지 않아 편리하다.)
-
start 노드와 end 노드가 집합에 모두 있다면 패스하고, 아니라면 집합에 삽입하고 가중치를 더해준다.
-
집합의 길이가
n
과 같다면 검사를 종료한다. MST 구성이 끝났기 때문.
4. 코드
def solution(n, costs):
answer = 0
costs = sorted(costs, key=lambda x : x[2]) #가중치가 작은 순서대로 정렬
con = set([0]) #방문한 노드 저장
while len(con) != n:
for s, e, v in costs:
if s in con and e in con: #이미 둘 다 방문했을 경우
pass
elif s in con or e in con:
con.add(s)
con.add(e)
answer += v
break
return answer
Author And Source
이 문제에 관하여([Programmers] 섬 연결하기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@tenykim1109/Programmers-섬-연결하기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)