문제풀이/백준
[백준]13418: 학교 탐방하기 - JAVA
빈둥벤둥
2021. 8. 12. 17:47
[백준]13418: 학교 탐방하기
13418번: 학교 탐방하기
입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 건물의 개수 N(1≤N≤1,000)과 도로의 개수 M(1≤M≤n*(n-1)/2) 이 주어진다. 입력의 두 번째 줄
www.acmicpc.net
풀이
🪑 MST를 활용한 문제였다. 최소 간선 트리를 구하는 MST를 활용하여 최대 간선 트리도 구해주면 된다.
📝 문제를 정리해 보자!
- 출발 건물은 0이며 항상 출발 건물에서 모든 건물로 갈 수 있다.
- 오르막길을 K번 오르면 피로도는 K^2이다.
- 최악의 피로도, 최소의 피로도를 가지는 경로의 피로도 차이를 구한다.
🔧 문제를 풀어 보자!
- 간선의 정보를 입력 받을 때 양 방향으로 정보를 입력 받는다.
- 최악의 피로도를 갖는 코스를 구해준다. 오르막길이 가장 많은 길을 선택하면 된다.
- 최소의 피로도를 갖는 코스를 구해준다. 오르막길이 가장 적은 길을 선택하면 된다.
🔹 간선의 정보를 입력 받는다.
- 양 방향으로 정보를 입력 받아 주어야 한다.
🔹 최악의 피로도를 갖는 코스를 구해준다. 오르막길이 가장 많은 길을 선택하면 된다.
- PRIM 알고리즘을 사용했다.
- 오르막길인 경우는 0이다. 즉, 최소 비용을 갖는 경로를 구해주면 그 경로가 오르막길이 가장 많은 경로가 된다.
🔹 최소의 피로도를 갖는 코스를 구해준다. 오르막길이 가장 적은 길을 선택하면 된다.
- 오르막길인 경우는 0이기 때문에 최대 비용을 갖는 경로를 구해주면 된다.
- 우선순위 큐를 내림차순으로 정렬하도록 변경해서 MST알고리즘을 똑같이 사용하여 풀어주었다.
코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
|
//13418: 학교 탐방하기
import java.io.*;
import java.util.*;
public class Main {
static int n, m;
static ArrayList<Node>[] list;
static PriorityQueue<Node> pq;
public static void main(String[] args) throws IOException {
//입력
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String str = bf.readLine();
StringTokenizer st = new StringTokenizer(str);
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
list = new ArrayList[n + 1];
for(int i = 0; i <= n; i++) {
list[i] = new ArrayList<>();
}
for(int i = 0; i < m + 1; i++) {
str = bf.readLine();
st = new StringTokenizer(str);
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
int road = Integer.parseInt(st.nextToken());
list[s].add(new Node(e, road));
list[e].add(new Node(s, road));
}
//입력 끝
pq = new PriorityQueue<>((o1, o2) -> o1.road - o2.road);
int worst_cost = (int) Math.pow(find_mst(0), 2); // 최악의 피로도 계산
pq = new PriorityQueue<>((o1, o2) -> o2.road - o1.road);
int best_cost = (int) Math.pow(find_mst(0), 2); //최소의 피로도 계산
System.out.println(worst_cost - best_cost);
}
public static int find_mst(int start) {
boolean[] visited = new boolean[n + 1];
pq.offer(new Node(start, -1));
int uphill_count = 0;
while(!pq.isEmpty()) {
Node current = pq.poll();
if(!visited[current.end]) visited[current.end] = true;
else continue;
if(current.road == 0) uphill_count++;
for(int i = 0; i < list[current.end].size(); i++) {
Node next = list[current.end].get(i);
pq.offer(next);
}
}
return uphill_count;
}
public static class Node {
int end, road;
public Node(int end, int road) {
this.end = end;
this.road = road;
}
}
}
|
cs |