Algorithm/MST

[백준 10423번] 전기가 부족해 (C++)

https://www.acmicpc.net/problem/10423 10423번: 전기가 부족해 첫째 줄에는 도시의 개수 N(1 ≤ N ≤ 1,000)과 설치 가능한 케이블의 수 M(1 ≤ M ≤ 100,000)개, 발전소의 개수 K(1 ≤ K ≤ N)개가 주어진다. 둘째 줄에는 발전소가 설치된 도시의 번호가 주어진다. 셋째 www.acmicpc.net 전기가 부족해 문제는 크루스칼/프림 알고리즘을 이용하여 해결할 수 있습니다. 모든 도시에 전기를 공급할 수 있도록 케이블을 설치하는 데 드는 최소 비용을 계산해야합니다. 따라서 발전소로부터 전기를 공급받는 그룹(G)에 모든 도시를 포함시켜야합니다. 발전소가 설치된 도시는 전기가 공급될 수 있기 때문에, 먼저, 그룹 G에 포함시킨 뒤, 비용이 낮은 간선부터..

[백준 1774번] 우주신과의 교감 (C++)

https://www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 우주신과의 교감 문제는 크루스칼/프림 알고리즘을 이용하여 해결할 수 있습니다. 이미 연결된 통로는 선택하고, 크루스칼이나 프림 알고리즘을 이용하여 나머지 간선을 선택하면 됩니다. 저는 크루스칼을 사용했습니다. ⚠️ 주의할 점 우주신의 좌표가 최대 1,000,000이므로, 거리를 계산할 때 1,000,000 * 1,000,000은 int형의 범위를 벗어날 수 있으므로 lo..

[백준 13418번] 학교 탐방하기 (C++)

https://www.acmicpc.net/problem/13418 13418번: 학교 탐방하기 입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 건물의 개수 N(1 ≤ N ≤ 1,000)과 도로의 개수 M(1 ≤ M ≤ N(N-1)/2) 이 주어진다. 입력의 두 번 www.acmicpc.net 학교 탐방하기 문제는 크루스칼/프림 알고리즘을 이용하여 해결할 수 있습니다. 최대한 내리막길로 이동하면 피로도를 가장 줄일 수 있고, 최대한 오르막길로 이동하면 피로도를 높일 수 있습니다. 내리막길로 내려갔다 다시 올라올 때 오르막이 되는 경우는 고려하지 않아도 되기 때문에, 오르막길의 비용을 내리막길보다 높게 설정하고, 최선의 경로를 파악할 때는 내리막길부터 ..

[백준 1647번] 도시 분할 계획 (C++)

https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 도시 분할 계획은 크루스칼/프림 알고리즘을 이용하여 해결할 수 있습니다. 모든 도시를 연결할 수 있는 최소 비용을 계산한 후, 연결한 길 중 하나를 제거하면 두 개의 마을로 만들 수 있습니다. 그 중 가장 비용이 높은 길을 제거하면, 최소의 비용으로 두 개의 마을을 유지할 수 있습니다. 아래는 크루스칼과 Union find를 이용한 코드입니다. #include..