목록크루스칼 알고리즘 (1)

국문과 유목민

[그래프] 도시 분할 계획

1. 문제 설명 마을을 2개로 나누려고 하는데 가장 효율적으로 나눌 수 있는 방법을 찾는 문제 - 핵심 아이디어는 전체 그래프에서 2개의 최소 신장 트리를 만들어야 한다. - 마을을 2개로 나누는 방법은 모든 그래프를 다 잇고난 이후 비용이 가장 큰 간선을 제거해주면 된다. - 정리하자면 크루스칼 알고리즘으로 최소 신장 트리를 찾은 뒤에 최소 신장 트리를 구성하는 간선 중 가장 비용이 큰 간선을 제거하는 것이다. 2. 코드 def find_parent(parent, x): if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return parent[x] def union_parent(parent, a, b): a = find_parent(pare..
알고리즘_코딩테스트/이것이 코딩테스트다 2021. 12. 8. 00:15
이전 Prev 1 Next 다음