최소스패닝트리3 [백준] 21924 도시건설 (Java) [21924 도시건설] 난이도: 골드4 21924번: 도시 건설 첫 번째 줄에 건물의 개수 $N$ $(3 \le N \le 10^5 )$와 도로의 개수 $M$ $(2 \le M \le min( {N(N-1) \over 2}, 5×10^5)) $가 주어진다. 두 번째 줄 부터 $M + 1$줄까지 건물의 번호 $a$, $b$ $(1 \le a, b \le N, a ≠ b)$와 두 www.acmicpc.net 문제 입력 출력 [아이디어] 모든 노드를 이었을 때 가중치가 최소가 되어야 하므로 MST를 사용하였다. 기본적인 MST를 활용하였는데 모든 건물이 연결되지 않은 경우도 있기 때문에 방문한 노드의 수를 체크해주었다. 모든 가중치를 계산한 후 방문한 노드의 수가 전체 노드의 수 보다 적다면 연결되지 않은 경.. 2022. 5. 14. [백준] 1647 도시 분할 계획 (Java) [1647 도시 분할 계획] 난이도: 골드4 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 문제 입력 출력 [아이디어] 우선 모든 마을을 유지비의 합의 최솟값으로 연결해준다. 즉 MST를 구해준다. 그 후 마을을 연견한 길 중 최대 유지비를 가진 길을 끊어주면 유지비의 합이 최소인 마을 2개를 구할 수 있다. [JAVA 코드] import java.io.BufferedReader; import java.io.IOException; import java.io.InputSt.. 2022. 3. 10. [백준] 1197 최소 스패닝 트리 (Java) [1197 최소 스패닝 트리] 난이도: 골드4 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 문제 입력 출력 [아이디어] 최소 스패닝 트리는 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 최소의 가중치 합을 가지는 그래프이다. MST 는 간적크, 간만프 -> 간선이 적으면 크루스칼, 간선이 많으면 크프림 알고리즘을 적용하는게 기본이지만 절대적이지는 않다. 하지만 나는 union, find를 활용하였다. [JAVA 코드] import java.io.B.. 2022. 3. 10. 이전 1 다음
