차곡차곡.

https://www.acmicpc.net/problem/10423 10423번: 전기가 부족해 첫째 줄에는 도시의 개수 N(1 ≤ N ≤ 1,000)과 설치 가능한 케이블의 수 M(1 ≤ M ≤ 100,000)개, 발전소의 개수 K(1 ≤ K ≤ N)개가 주어진다. 둘째 줄에는 발전소가 설치된 도시의 번호가 주어진다. 셋째 www.acmicpc.net 더보기 문제 세계에서 GDP가 가장 높은 서강 나라는 소프트웨어와 하드웨어 기술이 모두 최고라서 IT강국이라 불리고, 2015년부터 세상에서 가장 살기 좋은 나라 1등으로 꼽히고 있다. 살기 좋은 나라 1등으로 꼽힌 이후 외국인 방문객들이 많아졌고, 그에 따라 전기 소비율이 증가하여 전기가 많이 부족한 상황이 되었다. 따라서 서강 나라의 대통령은 최근 개..

먼저, 신장트리(Spanning Tree)란 방향성이 없는 N개 정점의 가중치 그래프에서 모든 정점을 연결하는 N-1개의 간선으로 구성된 트리를 말한다. 즉, 최소신장트리(MST: Minimum Spanning Tree)는 모든 정점을 연결하는 간선들의 가중치 합이 최소가 되는 신장트리를 찾는 것이다. MST를 구할 때 대표적으로 쓰이는 프림(Prim), 크루스칼(Kruskal) 알고리즘에 대해 알아보자. 프림(Prim) : 정점을 선택/미선택 집합으로 구별하고, 선택된 정점 미선택된 정점 사이의 간선 중 가장 작은 간선을 택하면서 정점을 연결해나가는 방법의 풀이이다. => 정점 중심 풀이 [풀이 순서] 1. 임의의 정점을 하나 선택. 2. 선택된 정점들로부터 인접한 아직 선택되지 않은 정점까지의 가장 ..

https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 더보기 문제 그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오. 최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다. 입력 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의..