[BOJ/백준] 14699 - 관악산 등산

14699번: 관악산 등산

---

Dynamic Programming

높은 위치부터 계산

---

---

• 제목

관악산 등산

---

• 조건

시간 제한 : 1 초

메모리 제한 : 512 MB 

---

• 문제

서울대학교에는 “누가 조국의 미래를 묻거든 고개를 들어 관악을 보게 하라”라는 유명한 문구가 있다. 어느 날 Unused는 Corea에게 조국의 미래를 물었고, Corea는 직접 관악산에 올라가 조국의 미래를 보고 답해 주기로 했다.

관악산의 등산로는 1부터 N까지의 서로 다른 번호가 붙어 있는 N개의 쉼터와 두 쉼터 사이를 오갈 수 있는 M개의 길들로 이루어져 있다. Corea는 지면에서부터 산을 오르는 것은 너무 귀찮다고 생각했기 때문에, 케이블카를 타고 임의의 쉼터에서 내린 다음 등산을 시작하기로 했다. Corea는 항상 더 높은 곳을 지향하기 때문에, 쉼터에 도착하면 그 쉼터와 직접 연결된 더 높은 쉼터로 향하는 길들 중 하나를 골라서 그 길을 따라 이동한다. 만약 그런 길이 없다면 등산을 마친다.

관악산의 쉼터들에는 조국의 미래를 볼 수 있는 전망대가 하나씩 설치되어 있다. Corea는 최대한 많은 쉼터를 방문해서 조국의 미래를 많이 보고 Unused에게 전해 주기로 했다. 관악산의 지도가 주어질 때, Corea가 각각의 쉼터에서 출발해서 산을 오를 때 최대 몇 개의 쉼터를 방문할 수 있는지 구하여라.

---

• 입력

첫 번째 줄에 등산로에 있는 쉼터의 수 N(2 ≤ N ≤ 5, 000)과 두 쉼터 사이를 연결하는 길의 수 M(1 ≤ M ≤ 100, 000)이 주어진다.

두 번째 줄에는 각 쉼터의 높이를 나타내는 N개의 정수가 번호 순서대로 주어진다. 각 쉼터의 높이는 1 이상 1, 000, 000 이하이며 서로 다르다.

세 번째 줄부터 M개의 줄에 걸쳐 각각의 길이 연결하는 두 쉼터의 번호가 공백으로 구분되어 주어진다. 쉼터의 번호는 1 이상 N 이하의 정수이다. 양 끝점이 같은 쉼터인 길은 없으며, 임의의 두 쉼터를 연결하는 길이 여러 개 존재할 수 있다.

---

• 출력

N개의 줄에 걸쳐 n번째 줄에 Corea가 n번 쉼터에서 출발해서 산을 오를 때 최대로 방문할 수 있는 쉼터의 개수를 출력한다.

---

예제 입력1	예제 출력1
5 5 3 1 6 4 7 1 4 2 1 3 4 4 2 5 1	3 4 1 2 1

---

• 힌트

2번 쉼터에서 출발하면 1번, 4번, 3번 쉼터를 차례대로 방문할 때 가장 많은 쉼터를 방문할 수 있다.

5번 쉼터는 3번 쉼터보다 높은 곳에 있지만 길 하나로 연결되어 있지 않으므로 3번 쉼터에서 5번 쉼터로 이동할 수 없다.

---

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

public class Main{
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;
    static int INF = 987564321;

    static class POINT implements Comparable<POINT>{
        int height, num;

        POINT(int num, int height){
            this.num = num;
            this.height = height;
        }

        @Override
        public int compareTo(POINT o) {
            return Integer.compare(o.height, this.height);
        }
    }

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        PriorityQueue<POINT> pq = new PriorityQueue<POINT>();

        st = new StringTokenizer(br.readLine());
        int height[] = new int[N + 1];
        for(int i = 1; i <= N; i++) {
            height[i] = Integer.parseInt(st.nextToken());
            pq.add(new POINT(i, height[i]));
        }

        HashMap<Integer, HashSet<Integer>> edge = new HashMap<Integer, HashSet<Integer>>();
        for(int i = 0; i < M; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            if(height[a] < height[b]){
                int temp = a;
                a = b;
                b = temp;
            }

            if(!edge.containsKey(a)) edge.put(a, new HashSet<Integer>());
            edge.get(a).add(b);
        }

        int answer[] = new int[N + 1];

        while(!pq.isEmpty()){
            int curr = pq.poll().num;
            answer[curr] = Math.max(answer[curr], 1);

            if(edge.containsKey(curr)){
                for(int next : edge.get(curr)){
                    answer[next] = Math.max(answer[next], answer[curr] + 1);
                }
            }
        }

        for(int i = 1; i <= N; i++){
            sb.append(answer[i]).append('\n');
        }
        System.out.println(sb);
    }
}