[Python/파이썬] 백준 14699번 관악산 등산

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번 쉼터에서 출발해서 산을 오를 때 최대로 방문할 수 있는 쉼터의 개수를 출력한다.

코드

from collections import deque
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
heights = [0] + list(map(int, input().split()))
graph = [[] for _ in range(n+1)]
dp = [1] * (n+1)
for _ in range(m):
    a, b = map(int, input().split())
    if heights[a] > heights[b]:
        graph[a].append(b)
    elif heights[a] < heights[b]:
        graph[b].append(a)

for i in range(1, n+1):
    q = deque([(i, 1)])

    while q:
        now, cnt = q.popleft()
        for nx in graph[now]:
            if dp[nx] < cnt+1:
                q.append((nx, cnt+1))
                dp[nx] = cnt+1

for i in range(1, n+1):
    print(dp[i])

 

DP+그래프 탐색을 이용하여 풀었던 문제였다.

위쪽에 위치한 쉼터에서부터 이동 가능한 아래쪽 쉼터들로 내려오면서 탐색을 할거다. 이를 위해서 처음에 연결된 쉼터들을 입력받을 때 graph[i]에 i번 쉼터에서 연결된 쉼터 중 더 아래쪽 쉼터들을 저장한다. 예를 들어 

그림에서 4번 쉼터에 연결된 쉼터 중 더 아래쪽의 쉼터는 1, 2번이다. 따라서 graph[4]의 값은 [1, 2]이다.

 

그런 다음에는 1~n번까지 하나씩 그래프 탐색을 진행한다.

1. deque에 시작점과 방문한 쉼터 개수 (i, 1)을 넣어준다.
2. q가 빌 때까지 다음 과정을 반복한다.
   1. q의 front 값 (now, cnt)을 popleft한다.
   2. now번 쉼터에서 이동 가능한 쉼터들을 하나씩 살펴보며 now에서 다음 쉼터(nx)로 가는 것이 nx에서 출발했을 때 가장 많은 쉼터를 방문할 수 있는 방법인 경우, q에 (nx, cnt+1)을 append하고 dp[nx]의 값도 cnt+1로 갱신해준다.
      무슨 말이냐면, dp[nx]에는 nx에서 출발했을 때 가장 많은 쉼터를 방문할 수 있는 방법을 저장할 것이다. 그렇기 때문에 현재 dp[nx]에 저장된 값보다 i번 쉼터에서부터 nx까지 오는데 방문한 쉼터의 개수인 cnt+1이 더 크다면 dp[nx]를 cnt+1로 바꿔주고 계속 탐색을 진행하기 위해 q에 (nx, cnt+1)를 넣어준다는 것이다. 만약 cnt+1이 더 작다면 이미 탐색한 다른 경로가 더 많은 쉼터를 방문한다는 것이므로 더이상 탐색을 진행할 필요가 없다.