[프로그래머스] 섬 연결하기 - 그리디(greedy) (python)

1. 문제 설명

n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.

다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.

---

2. 제한사항

• 섬의 개수 n은 1 이상 100 이하입니다.
• costs의 길이는 ((n-1) * n) / 2이하입니다.
• 임의의 i에 대해, costs[i][0] 와 costs[i] [1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i] [2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다.
• 같은 연결은 두 번 주어지지 않습니다. 또한 순서가 바뀌더라도 같은 연결로 봅니다. 즉 0과 1 사이를 연결하는 비용이 주어졌을 때, 1과 0의 비용이 주어지지 않습니다.
• 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
• 연결할 수 없는 섬은 주어지지 않습니다.

---

3. 입출력 예

 

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

 

---

4. 나의 풀이

문제를 보고 나서,,, 가중치가 있는 그래프는 오랜만이라 당황했다. 처음으로 그래프 순회를 해야하나? 생각해서 인접 행렬로 바꾸어서 생각해봤는데 도저히 어떻게 풀어야 할지 모르겠는거다. 그래서 구글에 가중 그래프를 검색해서 학부 때 배운 내용을 다시 한번 되새김질 했다. 가중치가 있는 그래프의 노드 순회는 최소 신장 트리를 이용해야 한다. MST는 kruskal 이나 prim 알고리즘을 이용하여 구현할 수 있는데,  이 문제를 kruskal 알고리즘을 이용하여 풀어보기로 했다.

 

최소 신장 트리 (MST: Minimum Spanning Tree)란?
Spanning Tree(그래프 내의 모든 정점을 포함하는 트리) 중에서 사용된 간선들의 가중치 합이 최소인 트리

 

 

출처: https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html

 

kruskal 알고리즘은 다음과 같이 구현할 수 있다.

 

1. 간선의 가중치를 기준으로 오름차순으로 정렬한다.
2. 정렬된 간선 목록에서 사이클을 만들지 않는 간선을 차례대로 선택한다.
3. 모든 노드를 지난 경우 반복을 종료한다.

 

def solution(n, costs):
    costs.sort(key = lambda x:x[2])
    ans = costs[0][2]
    visited = set([costs[0][0], costs[0][1]])
    costs.pop(0)
    
    i = 0    
    while(len(visited) < n):
        if costs[i][0] in visited or costs[i][1] in visited:
            if costs[i][0] in visited and costs[i][1] in visited:	#사이클은 만들지 않는다
                i += 1
                continue
            ans += costs[i][2]
            visited = visited.union(costs[i][:2])
            del costs[i]
            i = 0
            continue
        i += 1

    return ans

 

여러 반례들을 따져가며 오랜 시간이 지난 후 통과할 수 있었다. 원래 코테 문제를 풀때에는 시간을 고려해서 풀어야 하는데 조금만 더 조금만 더 하다가 결국 생각했던 시간보다 훨씬 더 지나 풀어버렸다. 혼자 힘으로 알고리즘을 푼 것은 좋지만 빠르고 효율적으로 알고리즘을 생각해 내야 하는 실전에는 그다지 좋은 결과는 아니라고 생각한다. 하지만 잊고있던 알고리즘 몇가지를 다시 공부할 수 있어서 좋게 생각하기로 했다. 앞으로는 딱 1시간만 고민하고 풀리지 않으면 힌트를 찾아가면서 해결해야겠다...

 

 

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/42861

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