프로그래머스 - 섬 연결하기(Level 3)/Wanna Be 컴잘알

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

입출력 예

n	costs	return
4	[[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]	4

입출력 예 설명

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

 

-설명-

 

1. 탐욕적인 방법(greedy method) 을 이용하여 네트워크(가중치를 간선에 할당한 그래프)의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 크루스칼 알고리즘을 사용하면된다.

2. 크루스칼 알고리즘을 구현하는 대표적인 방법은 어떤 임의의 지점을 시작으로 해당 지점과 연결된 가장 적은 비용을 갖는 간선을 선택하는 것이다. (단, 그 최소비용 간선이 선택됐을때 사이클이 형성되면 안 된다.)

사이클 형성 

 *사이클 형성이란? gd 간선을 선택하게되면 g->b->c->d->g의 사이클이 형성된다.

3. 시작노드는 costs[0][0]으로 설정하고 node라는 리스트에 지금까지 도착했던 node들을 넣어준다.

4. node리스트에 들어간 노드와 연결된 노드 중에 가장 최소 간선을 넣는다.

   (단, 사이클이 형성되는 노드인 경우 무시한다.)

5. node에 최소 간선의 노드들을 삽입해주고 중복을 없애준다.

6. answer 에 비용을 누적시켜줘 최종적으로 node에 모든 노드들이 들어오면 해당 값을 리턴시켜준다. 

 

-코드-

def solution(n, costs):
    answer = 0
    node = []
    node.append(costs[0][0])
    
    while len(node)!=n:
        idx = 0
        minCost = 2000000000
        for i,value in enumerate(costs):
            if value[0] in node or value[1] in node:
                if value[0] in node and value[1] in node: #사이클 형성인 경우
                    continue
                if minCost > value[2]:
                    minCost = value[2]
                    idx = i
        
        node.append(costs[idx][0])
        node.append(costs[idx][1])
        node = list(set(node))
        costs.pop(idx)
        answer += minCost

    return answer

 

크루스칼 이미지 출처 : https://gmlwjd9405.github.io/2018/08/29/algorithm-kruskal-mst.html