[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이 없어야 하는건 크루스칼과 같다.

여기서는 좀 더 직관적인 방법인 크루스칼을 사용하면 문제가 해결된다.

1. costs 배열을 가중치가 작은 순서대로 정렬한다.

2. 방문한 노드들을 저장할 집합을 생성한다. (집합은 중복이 허용되지 않아 편리하다.)

3. start 노드와 end 노드가 집합에 모두 있다면 패스하고, 아니라면 집합에 삽입하고 가중치를 더해준다.

4. 집합의 길이가 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