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

문제링크 : https://www.acmicpc.net/problem/14699

14699번: 관악산 등산

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321; 
const int MOD = 1000000;

int N, M;
int arr[5001];
int result[5001];
vector<int>v[5001];

int func(int idx, int h)
{
    if(result[idx]) return result[idx]; //중복방지
    result[idx]=1; //기본값 1
    
    for(int i=0; i<v[idx].size(); i++)
    {
        int next = v[idx][i]; //다음 위치
        if(arr[next] > h) //연결된 다음 위치의 높이가 더 크면
        {
            result[idx] = max(result[idx], func(next, arr[next])+1); //연결된 값들을 기준으로 +1
        }
    }
    return result[idx]; //해당 인덱스에 대한 최대 쉼터 반환
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N >> M;
    for(int i=1; i<=N; i++) cin >> arr[i];

    while(M--)
    {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b); //양방향
        v[b].push_back(a);
    }

    for(int i=1; i<=N; i++)
    {
        cout << func(i, arr[i]) << "\n";
    }

    return 0;
}

 

 

현재 인덱스와 해당 인덱스 위치의 높이를 기반으로 연결된 값들을 탐색한다.

현재 인덱스에 연결된 값의 높이가 현재 높이보다 크다면 이어서 탐색하게 된다.

 

쉼터의 갯수는 최소값으로 자기 자신이 있기에 1로 초기화하고 위의 높이 기준을 통과할때마다 탐색을 통해 갱신하게 된다.

이를 위한 함수에 인덱스와 높이를 넘겨주기 때문에 다음 값을 탐색 할때 다음 인덱스 next와 해당 인덱스의 높이인 arr[next]를 넘겨주게 된다.

이 2개의 값을 넘겨준 결과값에 + 1을 해준 것과 현재 쉼터 갯수를 비교하여 더 큰 것을 갱신하게 되는데,

여기서 + 1이 다음 쉼터로 이동이 가능한 상태이기떄문에 쉼터의 갯수가 늘어나는 것을 의미한다.

시작 인덱스를 기준으로 재귀를 돌며 계속해서 조건을 만족하는 연결된 값들이 있다면 쉼터의 갯수가 그만큼 늘어나게 된다.

 

중복된 것 (시간초과) 방지를 위하여 만약 이미 탐색한 인덱스에 대해 다시 접근했을 경우는 바로 반환해주도록 한다.