[Gold V] 관악산 등산 - 14699

문제 링크

성능 요약

메모리: 47396 KB, 시간: 228 ms

분류

다이나믹 프로그래밍, 그래프 이론

문제 설명

서울대학교에는 “누가 조국의 미래를 묻거든 고개를 들어 관악을 보게 하라”라는 유명한 문구가 있다. 어느 날 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. 선택된 휴식지보다 높아야 한다.
2. 더 많은 길을 지나갈 수 있어야 한다.

선행 조건으로는 그래프를 만들어서 연결성을 부여해주어야한다.
보통 그래프를 구현할 때에는 인접행렬 또는 인접리스트로 구현 가능하다.

그래프를 구현할 때 최대 크기를 계산해보면 $N \times M$이며, 최대 $5\times 10^8$의 크기가 구현이 되어야 한다. 대략 200MB 정도이다.

재귀함수로 구현하기로 하였고 과정은 아래와 같다.

1. 자기보다 높은 쉼터까지 가는 모든 길을 선택한다
2. 방문 크기를 1 증가한다.
3. 방문한 쉼터 중 더 큰쪽을 result로 선택한다.
4. 더이상 방문할 곳이 없다면 1 리턴

이를 구현한것이 아래 코드이다.

n, m = map(int, input().split())
height = [0] + list(map(int, input().split()))
graph = [[] for _ in range(m + 1)]

for i in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

def find(s):
    result = 1
    for ss in graph[s]:
        if height[ss] > height[s]:
            result = max(find(ss) + 1, result)
    return result

for i in range(1, n+1):
    print(find(i))

이 경우에는 중복되는 부분 문제가 존재하며, 그래프가 동일하다면, 함수의 참조적 투명성이 보장되므로, 메모이제이션을 적용할 수 있다.

앞선 방문에서 이미 답이 나와있는 노드의 경우 답을 저장하는 방식으로 메모이제이션을 구현한다.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(int(1e8))
n, m = map(int, input().split())
height = [0] + list(map(int, input().split()))
graph = [[] for _ in range(m + 1)]
dp = [-1 for _ in range(n+1)]

for i in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

def find(s):
    if dp[s] != -1:
        return dp[s]
    result = 1
    for ss in graph[s]:
        if height[ss] > height[s]:
            result = max(find(ss) + 1, result)
    dp[s] = result
    return dp[s]

for i in range(1, n+1):
    print(find(i))

이 코드는 Index Error로 종료되었다. grpah에 대한 코드를 수정하니 해결되었다.

코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(int(1e8))
n, m = map(int, input().split())
height = [0] + list(map(int, input().split()))
graph = [[] for _ in range(100001)]
dp = [-1 for _ in range(n+1)]

for i in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

def find(s):
    if dp[s] != -1:
        return dp[s]
    result = 1
    for ss in graph[s]:
        if height[ss] > height[s]:
            result = max(find(ss) + 1, result)
    dp[s] = result
    return dp[s]

for i in range(1, n+1):
    print(find(i))

---

회고

구상하고 코드로 구현하는데까지 크게 어렵지 않았던 문제, 다만 최단거리나 그런 종류의 문제로 착각할 수 있을법함. 문제를 받으면 차근차근 문제를 따라가는 습관을 가질 필요가 있다.