목록그래프_알고리즘 (1)

국문과 유목민

[그래프이론] 어두운 길

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다. 문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다. 소요시간: 20분 1. 문제 설명 - 마을에 설치되어 있는 가로수를 줄여서 비용을 줄이려고 한다. 가로수를 줄였을 때 절약할 수 있는 금액의 최대를 출력하는 문제 2. 접근 방식 - 최소비용으로 모든 노드를 연결하는 문제(크루스칼 알고리즘) - 추후 간선의 길이가 길어질 것을 대비해 heapq를 활용해서 구해봤다. 3. 코드 def find_parent(parent, a): if parent[a] != a: parent[a] = find_parent(parent, parent[a]) return parent[a] def union_parent(parent,..
알고리즘_코딩테스트/이것이 코딩테스트다 2021. 12. 27. 22:52
이전 Prev 1 Next 다음