https://school.programmers.co.kr/learn/courses/30/lessons/42861
내 풀이
1. 섬들을 모두 연결해야하고 이 때 최소 비용으로 연결하는 방법을 찾는다면 크루스칼 알고리즘을 사용할 수 있다
2. 섬들을 연결하는 비용으로 정렬한다
3. 적은 비용부터 하나씩 탐색하여 연결된 부모 노드를 찾거나 부모노드라면 더 작은 노드로 값을 바꾼다
def solution(n, costs):
def getparent(parent,n):
if parent[n]!=n:
parent[n]=getparent(parent,parent[n])
return parent[n]
def union_parent(parent,a,b):
a=getparent(parent,a)
b=getparent(parent,b)
if a>b:
parent[a]=b
else:
parent[b]=a
answer = 0
costs.sort(key=lambda x:x[2])
parent=[i for i in range(n)]
for a,b,cost in costs:
if getparent(parent,a)!=getparent(parent,b):
union_parent(parent,a,b)
answer+=cost
return answer
다른 풀이
def solution(n, costs):
costs = sorted(costs, key=lambda x:x[2])
node = set([costs[0][0], costs[0][1]])
answer = costs[0][2]
while len(node) != n:
for i in range(1, len(costs)):
if costs[i][0] in node and costs[i][1] in node:
continue
if costs[i][0] in node or costs[i][1] in node:
node.update([costs[i][0], costs[i][1]])
answer += costs[i][2]
break
return answer
배운 점
1. 크루스칼 알고리즘에 대해 학습했다
2. 모든 곳을 연결하고 최저비용으로 한다면 크루스칼 알고리즘을 적용시킬 수 있다
크루스칼 알고리즘에 대해 학습을 원하는 분들은 아래 글을 참고하시면 됩니다
2023.05.22 - [IT] - [알고리즘] 크루스칼 알고리즘
반응형
'Algorithm > 프로그래머스' 카테고리의 다른 글
[프로그래머스] 파이썬 문제풀이 - [1차] 뉴스 클러스터링 (0) | 2023.05.23 |
---|---|
[프로그래머스] 파이썬 문제풀이 - 여행경로 (1) | 2023.05.22 |
[프로그래머스] 파이썬 문제풀이 - 가장 먼 노드 (0) | 2023.05.19 |
[프로그래머스] 파이썬 문제풀이 - 피로도 (0) | 2023.05.19 |
[프로그래머스] 파이썬 문제풀이 - 행렬의 곱셈 (0) | 2023.05.16 |
댓글