Problem Solving/BOJ
13418. 학교 탐방하기
해스끼
2022. 12. 1. 20:19
코로나 새내기들에게 꼭 필요한 문제
13418번: 학교 탐방하기
입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 건물의 개수 N(1 ≤ N ≤ 1,000)과 도로의 개수 M(1 ≤ M ≤ N(N-1)/2) 이 주어진다. 입력의 두 번
www.acmicpc.net
학교 지도가 연결 그래프로 주어진다. 학교의 모든 건물을 탐방하는 경로 중 피로도가 최대일 때와 최소일 때의 차이를 구해야 한다. 피로도는 지나간 오르막길의 개수의 제곱으로 계산하므로, 오르막길을 가장 많이(또는 적게) 지나가는 경우를 구해야 한다.
건물 $N$개와 입구까지 총 $N+1$개의 노드를 연결하는 트리에는 간선이 $N$개 존재한다.
지문은 거창하지만, 그냥 최소 스패닝 트리 문제이다. 피로도가 최대인 경우를 계산하려면 오르막길과 내리막길의 가중치를 각각 0과 1로 두고 MST를 만들면 된다. 만든 MST의 가중치의 합은 내리막길의 수와 같으므로, 구한 값을 $N$에서 빼면 오르막길의 개수를 구할 수 있다. 이 값을 $h_{1}$이라 하자.
피로도가 최소인 경우를 계산하려면 오르막길과 내리막길의 가중치를 서로 바꿔서 계산하면 된다. 그러면 MST에 포함되는 오르막길의 수를 바로 구할 수 있다. 이 값을 $h_{2}$라 하자.
마지막으로 $(h_{1})^{2} - (h_{2})^{2}$를 출력하기만 하면 된다. 참 쉽죠?
재밌어 보여서 골랐는데, 그냥 구현 문제였네..