본문 바로가기

최소신장트리3

[백준] 최소 스패닝 트리(1197) Java, Prim 알고리즘 문제 링크 https://www.acmicpc.net/problem/1197 문제 요약 더보기 그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오. 최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다. 입력 더보기 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다. 그래프의 정점은 1번부터 V번까지 번호가 매겨.. 2021. 8. 30.
[백준] 유럽여행(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.

티스토리툴바