[BOJ][🟡5][백준#14699] 관악산 등산

문제 출처

BAEKJOON Online Judge #14699

문제

서울대학교에는 “누가 조국의 미래를 묻거든 고개를 들어 관악을 보게 하라”라는 유명한 문구가 있다. 어느 날 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번 쉼터에서 출발해서 산을 오를 때 최대로 방문할 수 있는 쉼터의 개수를 출력한다.

예제

입력

5 5
3 1 6 4 7
1 4
2 1
3 4
4 2
5 1

출력

3
4
1
2
1

My Sol

import sys
input = sys.stdin.readline

V, E = map(int, input().split())
hs = [0] + list(map(int, input().split()))
hs2 = []
for i, h in enumerate(hs):
    hs2.append([h, i])
hs2.sort(reverse=True)


cnts = [0]*(V+1)
G = [set() for _ in range(V+1)]
for _ in range(E):
    u, v = map(int, input().split())
    if hs[u] > hs[v]:
        u, v = v, u
    G[u].add(v)


for i in range(V):
    s = hs2[i][1]
    max_cnt = 0
    for k in G[s]:
        max_cnt = max(max_cnt, cnts[k])
    cnts[s] = max_cnt + 1

for i in range(1, V+1):
    print(cnts[i])

DP는 아니지만, DP의 방식을 일부 활용해서 중복 계산을 줄였다. 높이가 높은 순으로 정렬해서 해당 쉼터보다 높은 위치에 인접한 쉼터 중 누적된 이동 가능 쉼터 개수의 최댓값을 계산하고 이에 자기 자신인 1을 더해 cnts에 저장하는 방식이다.

이를 통해 아래에 있는 쉼터는 위로 연결된 쉼터마다 매번 이동 경로를 계산할 필요가 없어진다.

결과

맞았습니다!!