[Python] Progrmmers 코딩테스트 연습 : 섬 연결하기 (Greedy, Kruskal)

---문제---

 

문제 설명

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

입출력 예

n  costs return

4

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

4

 

---코드---

 

본 문제는, 크루스칼(Kruskal)알고리즘을 이용하여 푸는 문제입니다.
Kruskal 알고리즘이란 ? 탐욕적 기법(Greedy)를 이용하여 네트워크의 모든 노드들을 Cycle 없이 최소 비용으로 연결하는
최적의 비용을 구하는 것입니다.

따라서, 정답 알고리즘의 과정을 다음과 같습니다.
STEP 1. 처음 시작 하는 노드의 연결된 간선들을 모두 찾습니다.
STEP 2. 그 중에서 제일 비용이 적은 간선을 채택하고, 그 간선에 포함된 노드 2개를 연결된 노드에 추가합니다.
            (연결된 노드 안에 그 노드가 이미 있으면 추가하지 않습니다.)
STEP 3. 연결된 노드에 있는 노드들과 연결된 간선들 중에서 제일 비용이 작은 간선을 선택하여 STEP 2 를 반복합니다.

STEP 4. 모든 노드들이 연결된 노드에 포함되어 있을 때 (len(check)==n) 비교를 끝내고 정답을 리턴합니다.

 

def solution(n, costs):
    answer = 0
    check = [costs[0][0]]

    while(len(check)!=n):
        min_dis=0
        min_idx = 0
        min_des = 0
        for i,cost in enumerate(costs):
            if(cost[0] in check and cost[1] not in check):
                if(min_dis==0 or cost[2]<min_dis):
                    min_dis = cost[2]
                    min_idx = i
                    min_des = cost[1]
            elif(cost[1] in check and cost[0] not in check):
                if(min_dis==0 or cost[2]<min_dis):
                    min_dis = cost[2]
                    min_idx = i
                    min_des = cost[0]
        answer = answer + min_dis
        del costs[min_idx]
        check.append(min_des)

    return answer

 

---출처---

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

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