처음에는 단순한 욕심 문제인 줄 알고 풀었습니다.
그러나 이것이 탐욕 문제에 대한 해결책이라고 가정하면 최소한의 비용으로 다리를 건너지 못할 수도 있습니다.
이를 해결하려면 MTS 알고리즘을 사용하여 해결해야 합니다.
'추천 관련글,
MTS 알고리즘은 그래프 관련 알고리즘으로 BFS와 그리디 알고리즘을 결합한 알고리즘으로 생각하시면 좋습니다.
def solution(n, costs):
answer = 0
#다리를 건설하는 비용을 작은 순으로 정렬해줍니다.
costs.sort(key=lambda x:x(2))
#처음 시작하는 노드를 넣어줍니다.
graph = set((costs(0)(0)))
#최소의 비용으로 모든 섬을 통행할 수 있도록 모든 노드에서 모든 경로를
#순회하며 비용이 가장 적은 곳으로 갈 수 있도록 반복문을 선택해줍니다.
while len(graph) !
= n:
for i in costs:
#이미 다녀온 노드라면 패스
if i(0) in graph and i(1) in graph:
continue
#둘 중에 하나라도 안 가본 곳이라면 최소 값을 더해줍니다.
if i(0) in graph or i(1) in graph:
graph.update((i(0), i(1)))
answer+=i(2)
break
return answer다음과 같이 해결하여 해결할 수 있습니다.
- 비용을 기준으로 에지를 정렬합니다.
이 경우 Python의 sorted() 함수와 Lambda 함수를 사용하여 쉽게 정렬할 수 있습니다. - 비용이 가장 낮은 에지를 선택하여 다이어그램에 추가합니다.
이 시점에서 그래프는 선택된 노드 집합으로 구현됩니다. - 비용이 가장 작은 에지가 그래프의 노드 수가 그래프의 노드 수와 같아질 때까지 순서대로 선택됩니다.
선택한 Edge의 양쪽 끝이 다이어그램에 포함되어 있으면 선택되지 않고 하나만 포함되어 있으면 다이어그램에 추가됩니다.
이 시점에서 선택한 에지의 비용이 응답에 추가됩니다.