[백준]13418: 학교 탐방하기 - JAVA

[백준]13418: 학교 탐방하기

13418번: 학교 탐방하기

풀이

🪑 MST를 활용한 문제였다. 최소 간선 트리를 구하는 MST를 활용하여 최대 간선 트리도 구해주면 된다.

 

📝 문제를 정리해 보자!

• 출발 건물은 0이며 항상 출발 건물에서 모든 건물로 갈 수 있다.
• 오르막길을 K번 오르면 피로도는 K^2이다.
• 최악의 피로도, 최소의 피로도를 가지는 경로의 피로도 차이를 구한다.

 

🔧 문제를 풀어 보자!

1. 간선의 정보를 입력 받을 때 양 방향으로 정보를 입력 받는다.
2. 최악의 피로도를 갖는 코스를 구해준다. 오르막길이 가장 많은 길을 선택하면 된다.
3. 최소의 피로도를 갖는 코스를 구해준다. 오르막길이 가장 적은 길을 선택하면 된다.

 

 

🔹 간선의 정보를 입력 받는다.

- 양 방향으로 정보를 입력 받아 주어야 한다.

 

🔹 최악의 피로도를 갖는 코스를 구해준다. 오르막길이 가장 많은 길을 선택하면 된다.

- PRIM 알고리즘을 사용했다.

- 오르막길인 경우는 0이다. 즉, 최소 비용을 갖는 경로를 구해주면 그 경로가 오르막길이 가장 많은 경로가 된다.

 

🔹 최소의 피로도를 갖는 코스를 구해준다. 오르막길이 가장 적은 길을 선택하면 된다.

- 오르막길인 경우는 0이기 때문에 최대 비용을 갖는 경로를 구해주면 된다.

- 우선순위 큐를 내림차순으로 정렬하도록 변경해서 MST알고리즘을 똑같이 사용하여 풀어주었다.

 

 

코드

//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;
        }
    }
}