[백준][BOJ13418] 학교 탐방하기

Algorithm/Kruskal

by bedamino 2021. 6. 21. 23:18

1. 문제 : https://www.acmicpc.net/problem/13418

13418번: 학교 탐방하기

입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 건물의 개수 N(1≤N≤1,000)과 도로의 개수 M(1≤M≤n*(n-1)/2) 이 주어진다. 입력의 두 번째 줄

www.acmicpc.net

2. 풀이 : Kruskal

3. 시간복잡도 : O(ElogE)

4. 설명

문제의 조건은 다음과 같다.

1) 피로도 계산은 최초 조사된 길을 기준으로 한다.

2) 최악의 코스 = 오르막 길이 가장 많은 코스

3) 최적의 코스 = 오르막 길이 가장 적은 코스

각 간선에 오르막길인 경우엔 '0'을 내리막길인 경우엔 '1'의 가중치를 부여하고, 간선들을 가중치의 오름차순으로 정렬하여 최소 신장 트리를 생성하면 그림[1]과 같이 최악의 코스가 된다.

그림[1]의 최악의 코스에서 오르막길의 갯수는 3개이며, 피로도는 9가 된다.

간선들을 가중치의 내림차순으로 정렬하여 최대 신장 트리를 생성하면 그림[2]와 같이 최적의 코스가 된다.

그림[2]의 최적의 코스에서 오르막길의 갯수는 1개이며, 피로도는 1이 된다.

따라서, 최악의 코스와 최적의 코스의 피로도 차이는 8이 된다.

5. 코드

저작자표시 비영리 변경금지