[Baekjoon] 14699. 관악산 등산(Python)

14699번: 관악산 등산

 

문제

관악산의 등산로는 1부터 N까지의 서로 다른 번호가 붙어 있는 N개의 쉼터와 두 쉼터 사이를 오갈 수 있는

M개의 길들로 이루어져 있습니다.

 

관악산의 쉼터들에는 전망대가 하나씩 설치되어 있습니다. Corea가 각각의 쉼터에서 출발해서

산을 오를 때 최대 몇 개의 쉼터를 방문할 수 있는지 구해봅시다.

 

풀이

DFS(깊이우선탐색)을 이용해 풀 수 있는 문제입니다.

1. 특정 쉼터에서 출발해 자신보다 높은 쉼터로 이동해 가면서 더 이상 이동할 수 없을 때, 값을 반환합니다.

 

해당 쉼터에서 갈 수 있는 최대 쉼터의 개수는

1에서 구한 값들 중의 최대값에 1를 더한 값 입니다.

이러한 DFS를 각 쉼터를 출발점으로 해서 결과 값을 구할 수 있습니다.

 

코드

import sys
sys.setrecursionlimit(15000)
input = sys.stdin.readline

n, m = map(int, input().split())
height = [int(x) for x in input().split()]

maps = [[] for _ in range(n)]
for _ in range(m):
  s, e = map(int, input().split())
  maps[s-1].append(e-1)
  maps[e-1].append(s-1)

cache = [0]*n

def dfs(start):
  if cache[start] > 0:
    return cache[start]
  
  result = 0
  for end in maps[start]:
    if height[start] < height[end]:
      result = max(result, dfs(end))
  
  cache[start] = result + 1
  return cache[start]

answer = ''
for s in range(n):
  answer += ("%d\n" % dfs(s))
print(answer)