[백준/골드3] 13418. 학교 탐방하기

문제

---

문제

국민대학교 홍보대사 국희는 여름방학을 맞아 고등학생들을 대상으로 학교 내부에 있는 건물을 소개해주는 일을 하게 되어 학교 건물을 차례로 소개할 수 있는 이동 경로를 짜보기로 하였다. 국민대학교는 북한산의 정기를 받는 위치에 있어 건물 간 연결된 길이 험난한 오르막길일 수도 있고, 내리막길일 수도 있다. 국희는 먼저 입구를 기준으로 건물 간 연결된 도로가 오르막길인지, 내리막길인지를 파악하여 오르막길인 경우 점선, 내리막길인 경우 실선으로 표시하였다.

그림 1

건물을 구분하기 쉽도록 번호를 붙였고, 입구에는 숫자 0을 붙이기로 하였다. 그 다음 모든 건물을 방문하는 데 필요한 최소한의 길을 선택하여, 해당 길을 통해서만 건물들을 소개하기로 하였다. 이 과정은 굉장히 신중해야 하는데, 오르막길이 많이 포함되게 되면 굉장히 피곤해지기 때문이다.

얼마나 피곤해지는지 알아보기 위해 피로도를 계산하기로 하였다. 오르막길을 k번 오를 때, 피로도는 k2이 된다. 피로도의 계산은 최초 조사된 길을 기준으로만 한다. 즉, 내리막길로 내려갔다 다시 올라올 때 오르막길이 되는 경우는 고려하지 않는다. 입구는 항상 1번 건물과 연결된 도로를 가지며, 출발은 항상 입구에서 한다.

그림 2

그림 3

그림 1에서 모든 건물을 소개하기 위해 거쳐야 할 최소한의 도로는 4개임을 알 수 있다. 다음 2개의 그림은 그 4개의 도로를 뽑은 각각의 경우이다. 그림 2는 학교를 소개하는 데 총 3개의 오르막길을 오르게 되며 피로도가 9가 되는 최악의 코스가 된다. 그림 3은 오르막길을 1번만 오르게 되므로 학생들의 피로도는 1이 되는 최적의 코스가 된다. 이 경우 최악의 코스와 최적의 코스간 최종 피로도의 차이는 8이 된다. 국희는 최고의 프로그래머인 당신에게 위와 같은 방식으로 최악, 최선의 경로 간 피로도의 차이를 계산하는 프로그램의 제작을 부탁하였다. 프로그램을 작성하여 국희를 도와주자.

입력

입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 건물의 개수 N(1≤N≤1,000)과 도로의 개수 M(1≤M≤n*(n-1)/2) 이 주어진다. 입력의 두 번째 줄부터 M+1개의 줄에는 A, B(1≤ A,B ≤ N), C 가 주어진다. 이는 A와 B 건물에 연결된 도로가 있다는 뜻이며, C는 0(오르막길) 또는 1(내리막길)의 값을 가진다. 같은 경로 상에 2개 이상의 도로가 주어지는 경우는 없으며, 입구는 항상 1번 건물과 연결되어 있다. 입구와 1번 도로 간의 연결 관계는 항상 2번째 줄에 주어진다. 입구에서 모든 건물로 갈 수 있음이 보장된다.

출력

출력은 표준 출력을 사용한다. 입력받은 데이터에 대해, 주어진 조건을 만족하는 최악의 경로에서의 피로도와 최적의 경로 간 피로도의 차이를 출력한다.

풀이

---

접근방법

• 문제를 보자마자 MST 문제라고 생각했다.
• 최소 스패닝 트리
• 그 중 프림 + 우선순위 큐를 사용해야겠다고 생각
• 최악 코스 / 최적 코스 두가지를 선정해야 하니까 priority queue에서 데이터를 빼올 때 오르막길부터 빼오는 방식, 내리막길부터 빼오는 방식 두 방법이 필요하다.
• Comparable 상속 받아서 데이터 클래스를 만들 때 오르막길 먼저 정렬하는 방식, 내리막길을 먼저 빼오는 방식 두가지로 구현했다.

코드

---

package practice;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

// [골드3] 학교 탐방하기
// MST
public class baekjoon_13418 {
    static int N, M; // 건물 개수, 도로 개수
    static ArrayList<Data1>[] arr1;
    static ArrayList<Data2>[] arr2;
    static int Min, Max;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        arr1 = new ArrayList[N + 1];
        arr2 = new ArrayList[N + 1];
        for (int i = 0; i <= N; i++) {
            arr1[i] = new ArrayList<>();
            arr2[i] = new ArrayList<>();
        }

        for (int i = 0; i <= M; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int road = Integer.parseInt(st.nextToken());

            arr1[start].add(new Data1(end, road));
            arr1[end].add(new Data1(start, road));

            arr2[start].add(new Data2(end, road));
            arr2[end].add(new Data2(start, road));
        }

        prim1();
        prim2();

        System.out.println(Max - Min);

    }

    private static void prim1() {
        int K = 0;
        boolean[] visited = new boolean[N + 1];
        PriorityQueue<Data1> pq1 = new PriorityQueue<>();
        pq1.offer(arr1[0].get(0));
        visited[0] = true;

        int cnt = 0;
        while (!pq1.isEmpty()) {
            if (cnt == N) {
                break;
            }

            Data1 data1 = pq1.poll();

            if (visited[data1.to]) continue; // 이미 지나온 길이면 pass

            cnt++;
            visited[data1.to] = true;

            if (data1.road == 0) {
                K++;
            }

            int to = data1.to;

            for (int i = 0; i < arr1[to].size(); i++) {
                if (visited[arr1[to].get(i).to]) {
                    continue;
                } else {
                    pq1.offer(arr1[to].get(i));
                }
            }
        }
        Max = K * K;
    }

    private static void prim2() {
        int K = 0;
        boolean[] visited = new boolean[N + 1];
        PriorityQueue<Data2> pq2 = new PriorityQueue<>();
        pq2.offer(arr2[0].get(0));
        visited[0] = true;

        int cnt = 0;
        while (!pq2.isEmpty()) {
            if (cnt == N) {
                break;
            }

            Data2 data2 = pq2.poll();

            if (visited[data2.to]) continue; // 이미 지나온 길이면 pass

            cnt++;
            visited[data2.to] = true;

            if (data2.road == 0) {
                K++;
            }

            int to = data2.to;

            for (int i = 0; i < arr2[to].size(); i++) {
                if (visited[arr2[to].get(i).to]) {
                    continue;
                } else {
                    pq2.offer(arr2[to].get(i));
                }
            }
        }
        Min = K * K;
    }

    // 오르막길 먼저 정렬
    private static class Data1 implements Comparable<Data1> {
        int to;
        int road; // 오르막은 0 내리막은 1

        public Data1(int to, int road) {
            this.to = to;
            this.road = road;
        }

        @Override
        public int compareTo(Data1 o) {
            return this.road - o.road; // 오르막길 먼저
        }

        @Override
        public String toString() {
            return "Data1{" +
                    "to=" + to +
                    ", road=" + road +
                    '}';
        }
    }

    // 내리막길 먼저 출력
    private static class Data2 implements Comparable<Data2> {
        int to;
        int road; // 오르막은 0 내리막은 1

        public Data2(int to, int road) {
            this.to = to;
            this.road = road;
        }

        @Override
        public int compareTo(Data2 o) {
            return -this.road + o.road; // 내리막길 먼저
        }
    }
}

 

https://www.acmicpc.net/problem/13418

13418번: 학교 탐방하기