프로그래머스 Lv3 문제입니다. 실전에 대비하기 위해 60분 시간제한을 두고 풀었습니다.
문제
https://school.programmers.co.kr/learn/courses/30/lessons/42861
[나의 풀이]
⌛ 19분
def find_parent(parent,x):
if parent[x] != x:
parent[x] = find_parent(parent,parent[x])
return parent[x]
def union_parent(parent, start, end):
start_p = find_parent(parent,start)
end_p = find_parent(parent,end)
if start_p<end_p:
parent[end_p] = start_p
else:
parent[start_p] = end_p
def solution(n,costs):
answer = 0
parent = [i for i in range(n)]
costs = sorted(costs, key=lambda x:x[2])
for case in costs:
start, end , cost = case
if find_parent(parent,start) != find_parent(parent,end):
union_parent(parent,start,end)
answer += cost
return answer
연결해야하는 섬의 갯수(n)가 주어지고 섬을 연결하는 케이스별 비용 리스트(costs)가 주어질 때, 모든 섬을 연결할 수 있는 최소한의 비용을 구하는 문제입니다.🐥🐥🐥
Union-Find 알고리즘을 활용한 최소 신장 트리(크루스칼) 알고리즘의 대표적인 활용 사례로 이를 구현하여 풀었습니다.
먼저 현재 자신 노드의 부모 노드를 찾아내는 find_parent()라는 함수를 구현하고 부모 노드가 서로 다른 노드들을 통합하는 union_parent()함수를 선언해줍니다.
모든 섬을 연결하는 최소 비용을 구하는 문제이므로 어떠한 다리들을 연결했을 때, 가장 적은 비용이 드는 섬들부터 연결을 시작하기 위해 costs를 비용이 적은 순으로 정렬하였습니다.
이후 섬 연결 케이스별 비용(costs)을 순차적으로 돌며 find_parent()로 부모가 다른 섬들을 연결시키며 비용을 추가하는 방식으로 구현됩니다. 만약 부모가 같다면 이는 이미 연결된 섬이므로 비용을 추가하지 않게 됩니다.
[다른 사람의 풀이1]
def ancestor(node, parents):
if parents[node] == node:
return node
else:
return ancestor(parents[node], parents)
def solution(n, costs):
answer = 0
edges = sorted([(x[2], x[0], x[1]) for x in costs])
parents = [i for i in range(n)]
bridges = 0
for w, f, t in edges:
if ancestor(f, parents) != ancestor(t, parents):
answer += w
parents[ancestor(f, parents)] = t
bridges += 1
if bridges == n - 1:
break
return answer
'나의 풀이'처럼 크루스칼 알고리즘을 활용한 풀이입니다. ancestor() 함수를 통해 현재 자신의 부모 노드를 찾는 방식입니다. 🐁🐁🐁
한 가지 다른 점은 섬 연결 케이스별 비용(edges)(섬1, 섬2, 비용) 값들이 주어질 때, 섬1의 번호가 섬2의 번호보다 반드시 작다는 것을 이용하여 번호 비교없이 바로 섬2를 기준으로 부모를 초기화했다는 점입니다.
[다른 사람의 풀이2]
def solution(n, costs):
answer = 0
costs.sort(key = lambda x: x[2])
link = set([costs[0][0]])
# Kruskal 알고리즘으로 최소 비용 구하기
while len(link) != n:
for v in costs:
if v[0] in link and v[1] in link:
continue
if v[0] in link or v[1] in link:
link.update([v[0], v[1]])
answer += v[2]
break
return answer
연결된 섬별 최상위 부모 노드를 parent에 저장하는 형태가 아닌 set() 구조를 활용한 풀이입니다.🐕🐕🐕
적은 비용을 기준으로 정렬된 섬 연결 케이스별 비용(costs)을 돌며 현재까지 연결된 섬들(link)에 하나라도 연결되지 않은 섬(v[0] or v[1])이 있다면 두 섬(v[0], v[1])을 연결시키고 비용을 더하는 방식입니다.
find_parent(), union_parent() 함수를 따로 정의한 형태보다 while문, set()을 활용한 간결한 방식이었습니다.
감사합니다.