크루스칼2 [백준] 유럽여행(1185) Java 문제 링크 https://www.acmicpc.net/problem/1185 1185번: 유럽여행 첫 줄에는 방문할 나라의 수 N(5 ≤ N ≤ 10,000)과 이 나라들 사이를 연결하는 길의 수 P(N-1 ≤ P ≤ 100,000)가 주어진다. 두 번째 줄에는 N+1번째 줄까지 i+1번째 줄에는 i번째 나라를 방문할 때 드는 비 www.acmicpc.net 문제 요약 더보기 민식이는 여름에 유럽여행을 떠날 계획이다. 방문할 나라는 총 N개의 나라이고 편리하게 1번부터 N번까지 번호를 붙였다. 또한 이 나라들 사이에 이동 가능한 길은 M개가 있는데 민식이는 귀찮기 때문에 N개의 나라가 서로 연결된 것을 유지시키면서 최대한 많은 길을 지도에서 제거하고자 한다. 즉, N-1개의 길만을 남겨야할 것이다. 각 .. 2021. 8. 29. [야매 알고리즘] Kruskal 알고리즘 (MST 찾기), 백준 1197 최소 스패닝 트리 야매 알고리즘? 더보기 알고리즘의 정확한 정의나 의미를 다루지 않고 핵심적인 작동 원리와 코드 예제를 정리하기 위한 시리즈입니다. 전부 짚고 넘어가면 좋겠지만 그럴 지식도 없고, 공부하는 것보다 정리하는데 더 많은 에너지와 시간을 소모할 것 같아서, 기억을 되살리기 위한 아카이브 정도로만 사용할 수 있게 간단하게 정리할 예정입니다. 개요 MST(Minumum Spanning Tree)를 찾는데 사용되는 알고리즘. 임의의 connected graph가 주어졌을 때, greedy하게 간선을 선택하여 MST를 얻어낸다. MST란? Spanning tree는 graph 내의 모든 node를 포함하는 tree이다. Tree라는 것은 cycle이 없다는 것인데, cycle 없이 모든 node를 포함하려면 간선의 개.. 2021. 8. 26. 이전 1 다음
