[13418] 학교 탐방하기

 

 

문제정의

특정 학교를 탐방하는데.. 그 학교는 오르막과 내리막으로 구성되어있다.

학교내 모든 건물들을 정점, 그리고 그 건물사이의 길을 간선이라고 한다.

간선이 오르막일 경우 0, 내리막일 경우 1 으로 표시한다.

이 때 학교의 모든 건물을 다 탐색하고자 할 때, 오르막이 포함되면 피로도가 발생한다.

피로도는 탐색을 위한 트리에서 오르막이 포함된 횟수를 n 이라고 할 때, n^2 이다.

 

이때 최대 피로도를 가진 경우와 최소 피로도를 가진 경우,

즉 오르막을 가중치로 하는 최대 신장 트리와 최소 신장 트리 간의 피로도 차이를 구하는 문제이다.

 

코드

import java.io.*;
import java.util.*;

public class nam {

    static int n, m;
    static ArrayList<Node>[] list;
    static PriorityQueue<Node> pq;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.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 = br.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);    //o1 road, 오르막 우선시 
        int worst =  (int) Math.pow(Prim(0), 2); // 최악의 피로도 계산

        pq = new PriorityQueue<>((o1, o2) -> o2.road - o1.road);    //o2 road 내리막을 우선시
        int best = (int) Math.pow(Prim(0), 2); //최소의 피로도 계산
        System.out.println(worst - best);
    }

    public static int Prim(int start) {
        boolean[] visited = new boolean[n + 1];
        pq.offer(new Node(start, -1));

        int upper_cnt = 0;
        while(!pq.isEmpty()) {
            Node current = pq.poll();

            if(!visited[current.end]) visited[current.end] = true;
            else continue;

            if(current.road == 0) 
                upper_cnt++;   //오르막 체크
            for(int i = 0; i < list[current.end].size(); i++){
                Node next = list[current.end].get(i);
                pq.offer(next);
            }
        }
        return upper_cnt;   //MST찾고 그 오르막 횟수만큼 체크 해서 리턴함
    }
    //Prim 통한 MST찾기 근데 기준은 피로도를 기준으로. 

    public static class Node {
        int end, road;

        public Node(int end, int road) {
            this.end = end;
            this.road = road;
        }
    }
}

 

Prim 알고리즘

Prim 은 방향성이 없는 그래프가 존재하고, 정점 사이에 가중치가 존재할 때 그래프의 모든 점을 가장 작은 Cost(비용) 으로 순회하는 MST 를 찾는 알고리즘 이다.

 

방식은 아래와 같다.

1. 임의의 정점을 선택한다.(A)

2. A 에 있는 노드와 A 에 없는 노드 사이의 간선 중 가중치가 최소인 간선을 찾는다.

3. 찾은 간선이 연결하는 두 노드 중, A 에 없던 노드를 포함시키고 그래프화 한다. (1에서 찾은 간선도 같이 T에 포함됩니다.)

4. 모든 노드가 그래프 T 에 포함될 때 까지 2, 3 를 반복한다.

 

위 문제에서는 오르막과 내리막을 가중치로 두었다. 가중치가 최소인 간선을 찾는것이 아니라 오르막과 내리막을 먼저 찾았던 것이다.