문제) 백준 - 최소 스패닝 트리 - 학교 탐방하기
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)
GitHub - Chocochip101/BOJ_Solution: BOJ Solutions
BOJ Solutions. Contribute to Chocochip101/BOJ_Solution development by creating an account on GitHub.
github.com
반응형
'PS(Problem Solving) > 백준_BOJ' 카테고리의 다른 글
| [백준] 12851번 - 숨바꼭질 2 (C++) 문제 및 풀이 (0) | 2022.03.01 |
|---|---|
| [백준] 15486번 - 퇴사 2 (C++) 문제 및 풀이 (0) | 2022.02.28 |
| [백준] 18243번 - Small World Network (C++) 문제 및 풀이 (0) | 2022.02.27 |
| [백준] 4779번 - 칸토어 집합 (C++) 문제 및 풀이 (0) | 2022.02.27 |
| [백준] 14400번 - 편의점 2 (C++) 문제 및 풀이 (0) | 2022.02.26 |
댓글