[백준] 14699번 : 관악산 등산 (C++)

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

 

 

 

 

 

풀이)

 

// 14699. 관악산 등산
#include <iostream>
#include <vector>
 
using namespace std;
 
int n, m;
vector<int> height(1, 0);
vector<vector<int>> vec;
 
int dp[5010];
 
int recur(int cur)
{
    // 기저조건
    // 더 이상 이동할 수 없을 때,
    // 1.연결 된 길이 1개 / 2. 1개 있는 길이 낮은 쉼터로 가는 길 
    if (vec[cur].size() == 1 && height[cur] >= height[vec[cur][0]])
    {
        return 0;
    }
 
    // 이미 구한 값이라면
    if (dp[cur] != -1)
    {
        return dp[cur];
    }
 
    int ret = 0;
 
    for (int i = 0; i < vec[cur].size(); i++)
    {
        // 다음에 갈 곳의 높이를 구한다.
        int nxt_height = height[vec[cur][i]];
 
        // 다음에 갈 곳이 현재 위치보다 낮다면 continue
        if (height[cur] >= nxt_height) continue;
        
        // 이동할 수 있다면 +1 
        ret = max(ret, recur(vec[cur][i]) + 1);
    }
 
    dp[cur] = ret;
 
    return dp[cur];
}
 
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> m;
    vec.resize(n + 1, vector<int>());
 
    fill(&dp[0], &dp[5010], -1);
 
    int a, b;
    for (int i = 0; i < n; i++)
    {
        cin >> a;
        height.push_back(a);
    }
 
    for (int i = 0; i < m; i++)
    {
        cin >> a >> b;
        vec[a].push_back(b);
        vec[b].push_back(a);
    }
 
    for (int i = 1; i < n + 1; i++)
    {
        // 첫 쉼터도 카운트하므로 +1
        cout << recur(i) + 1 << "\n";
    }
 
    return 0;
}
 

---

출처 : https://www.acmicpc.net/problem/14699 

14699번: 관악산 등산