최소 스패닝 트리5 [백준] 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 내리막길로 갈 수 있는 최대 간선과 오르막길로 갈 수 있는 최대 간선의 차를 구하는 문제입니다. 모든 점을 잇는 간선을 뽑아야하므로 최소 스패닝 트리를 이용하여 간선을 선택합니다. 최대 간선은 정렬을 반대로 하여 Kruskal 알고리즘을 진행합니다. C++ 소스코드) Full Code) https://github.co.. 2022. 2. 27. [백준] 21924번 - 도시 건설 (C++) 문제 및 풀이 문제) 백준 - 최소 스패닝 트리 - 도시 건설 https://www.acmicpc.net/problem/21924 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 전형적인 최소 스패닝 트리 문제입니다. rank를 이용한 Disjointset과 kruskal 알고리즘을 이용하여 최소 비용을 구합니다. 비용의 개수로 모든 도시 연결 여부를 판단하여 -1 또는 절약 예산을 구합니다. C++ 소.. 2022. 1. 18. [백준] 4386번 - 별자리 만들기 (C++) 문제 및 풀이 문제) 백준 - 최소 스패닝 트리 - 별자리 만들기 https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 별자리를 이어 최소 비용으로 모두를 연결되게 만드는 문제였습니다. 모두가 연결되어야하고 최소 비용을 사용해야되므로 최소 스패닝 알고리즘으로 쉽게 해결할 수 있었습니다. C++ 소스 코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%201000~4999/4386.. 2021. 12. 12. [백준] 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 C++ 소스 코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%201000~4999/1647_%EB%8F%84%EC%8B%9C%20%EB%B6%84%ED%95%A0%20%EA%B3%84%ED%9A%8D.cpp GitHu.. 2021. 12. 9. [백준] 10021번 - Watering the Fields (C++) 문제 및 풀이 문제) 백준 - 최소 스패닝 트리(Minimum Spanning Tree) - Watering the Fields https://www.acmicpc.net/problem/10021 10021번: Watering the Fields Input Details There are 3 fields, at locations (0,2), (5,0), and (4,3). The contractor will only install pipes of cost at least 11. Output Details FJ cannot build a pipe between the fields at (4,3) and (5,0), since its cost would be only 10. He therefore b www.acmicpc.. 2021. 10. 14. 이전 1 다음 반응형
