[프로그래머스] 탐욕법(Greedy) 05. 섬 연결하기

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의 비용이 주어지지 않습니다.
• 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
• 연결할 수 없는 섬은 주어지지 않습니다.

 

입출력 예

 

입출력 예 설명

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

 

 

풀이

그리드 알고리즘을 이용하여 모든 섬을 연결하기 위해서는
1. 다리를 건설하는 비용 순서대로 정렬한다.
2. 가장 적은 비용이 들어가는 다리를 선택한다.
3. 해당 다리가 cycle (다른 다리를 통하여 이미 연결되어 있는 다른 섬을 연결)을 생성하는지 체크한다.

2~3번을 반복하여 모든 섬들이 연결되면 종료한다.
모든 섬이 연결 되어있는지는 3번으로 cycle을 생성하지 않기 때문에 n-1개의 다리만 있으면 모든 섬을 연결할 수 있다.

위의 방법대로 구현하기 위해서 union-find를 이용하는 kruskal algorithm을 이용하였다.
각 섬들을 독립적인 set으로 설정한 뒤 최소의 비용이 드는 다리를 선택할때마다
해당 섬들을 같은 set으로 묶어서 연결하였다.

 

def find(start) :
        if start != p[start]:
            p[start] = find(p[start])
        return p[start]

find 함수를 이용하여 해당 섬의 root에 해당하는 섬을 p list에 저장한다.

 

def union(start, end):
        p[find(end)] = find(start) 
        #end의 root를 start root로 설정 , 두 집합을 합침

union 함수를 이용하여 서로 다른 2개의 set을 하나로 합친다.

 

전체 코드

def solution(n, costs):
    answer = 0
    
    costs.sort(key = lambda x : x[2])
    
    p = [] # 연결된 섬들의 집합
    edge = 0 # edge의 갯수
    
    
    def find(start) :
        if start != p[start]:
            p[start] = find(p[start])
        return p[start]

    def union(start, end):
        p[find(end)] = find(start) 
        #end의 root를 start root로 설정 , 두 집합을 합침
    
    for i in range(n+1):
        p.append(i)
        
    while True :
        if edge == n - 1 : #모든 섬이 연결되는 다리의 갯수
            break
        start , end , cost = costs.pop(0)
        if find(start) != find(end):
            union(start,end)
            answer += cost
            edge += 1
    
    return answer