[백준 14699] 관악산 등산

최근 다시 푸니 결과는 더 좋은거 같은데

접근 방식이 아예 달라서 둘 다 기록해 놓는다

 

---

1. 방향 그래프 + DFS + DP 사용

 

우선 높이가 낮은 곳에서 높은 곳으로 밖에 못올라가므로
방향 그래프로 저장해준다

그 이후 각 노드를 시작점으로 하여 dfs를 통해
각 노드를 시작점으로 삼았을 시 얼마나 올라갈 수 있는지 계산해준다

이때 dfs를 재귀적으로 돌때 이미 계산이 된 노드들은 다시 계산이 안되도록
dp 배열을 통해 기록해놓는게 핵심이다

 

#include <iostream>
#include <vector>
#include <bitset>

#define SIZE 5001

using namespace std;

int N, M;
int height[SIZE];
int ans[SIZE]; // visited를 ans가 -1인 것으로 판단가능함
vector<vector<int>> graph(SIZE);

int solve(int cur)
{
    // leaf node 면
    if(graph[cur].size() == 0){
        ans[cur] = 1;
        return 1;
    }

    // 이미 계산되어 있으면 (이미 방문했으면)
    if(ans[cur]!=-1){
        return ans[cur];
    }

    int sum = -1;

    int next;
    int temp;
    for (int i = 0; i < graph[cur].size(); i++)
    {
        next = graph[cur][i];

        // 이미 방문한 곳이면
        if(ans[next]!=-1){
            if(ans[next] > sum){
                sum = ans[next];
            }
        }
        else{
            temp = solve(next);
            if (temp > sum)
            {
                sum = temp;
            }
        }
    }

    ans[cur] = sum + 1;
    return ans[cur];
}

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

    cin >> N >> M;

    for (int i = 1; i <= N;i++){
        cin >> height[i];
    }

    int start, end;
    for (int i = 0; i < M; i++)
    {
        cin >> start >> end;

        // 높이에 따라 방향그래프로 표현
        if(height[start] < height[end]){
            graph[start].push_back(end);
        }else{
            graph[end].push_back(start);
        }
    }

    // ans 배열 초기화
    for (int i = 1; i <= N;i++){
        ans[i] = -1;
    }

    // 모든 정점에 대해 dfs
    for (int i = 1; i <= N; i++)
    {
        solve(i);
    }

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

    return 0;
}

 

---

2. 우선순위 큐 사용

 

우선 처음에는 모든 지점에 대한 값을 다 구해야하나 생각했다.

하지만 항상 자기보다 높이 있는 지점으로 올라갈 수 밖에 없다는 조건이 dp에 대한 힌트였다.

 

만약 A 쉼터의 값을 찾고 싶으면 A 쉼터보다 높이 있는 쉼터의 답에 자기자신인 +1을 해주면 된다.

이러면 브루트포스로 중복계산하지 않고도 답을 구할 수 있다.

그리고 이렇게 중복계산을 하지 않고 이미 계산한 것들을 활용하는 비법이 dp이다.

 

그래서 이 문제는 그래프 + dp 문제이다

사실 그래프 이론이 쓰이지도 않았다.

그냥 그래프는 표현만 해주면 된다.

 

가장 높은 놈은 1로 해주고 

높은 놈들부터 차례대로 내림차순으로 순회해나가면서

자기보다 높이 있는 놈들 중 가장 높은 값을 가진 놈을 찾아서 +1 한 값을 저장해주면된다.

 

참고로 unique할때 routes[i]로 해야하는데 routes로 써놔서 1시간동안 헤맸다... 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

#define SIZE 5001

using namespace std;

int N, M;

int height[SIZE];
vector<vector<int>> graph(SIZE);

// 높이대로 내림차순 정렬
priority_queue<pair<int, int>> pq;
int ans[SIZE] = { 0, };

// pq를 높이로 정렬했으니
// 높이가 높은 것부터 시작할 수 밖에 없음
void solve()
{
    while (!pq.empty())
    {
        int curnode = pq.top().second;
        pq.pop();

        // 자기보다 위인 놈이 없으면
        if (graph[curnode].size() == 0)
        {
            ans[curnode] = 1;
        }
        // 자기보다 위인 놈들이 있으면
        // 그 중에 ans값 가장 큰놈 찾기
        else
        {
            for (int i = 0; i < graph[curnode].size(); i++)
            {
                int next = graph[curnode][i];
                if (ans[next] >= ans[curnode])
                {
                    ans[curnode] = ans[next] + 1;
                }
            }
        }
    }

    return;
}

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

    cin >> N >> M;
    for (int i = 1; i <= N; i++)
    {
        cin >> height[i];
        pq.push(make_pair(height[i], i));
    }

    int start, end;
    for (int i = 0; i < M; i++)
    {
        cin >> start >> end;
        if (height[start] < height[end])
        {
            graph[start].push_back(end);
        }
        else
        {
            graph[end].push_back(start);
        }
    }

    for (int i = 1; i <= N; i++)
        unique(graph[i].begin(), graph[i].end());

    solve();

    for (int i = 1; i <= N; i++)
        cout << ans[i] << " \n";

    return 0;
}