[BOJ 14699] 관악산 등산

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

쉼터에서 높은 곳으로만 이동이 가능할 때 각 쉼터에서 가장 많이 들릴수 있는 경우를 찾는 문제이다.

그냥 BFS를 톨리게 되면 시간초과가 나는데 왜나는지는 정확히 모르겠다 ㅠ 누가 설명좀 ;;; (그래서 계속틀림)

다른 방법으로는 DFS를 재귀적으로 접근하는 방법이었는데 나는 그렇게 안하고 위상정렬을 이용하였다. 

일단 쉼터들끼리 연결을 해주고, 그 이후에 자신으로 들어오는 간선이 없는 경우를 배열에 채워주는 방식으로 접근하였다. 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <cmath>
#include <stdio.h>
 
#define INF 1e9
typedef long long ll;
using namespace std;
 
int n,m,h[111111],dp[111111],cnt[111111];
bool visit[111111];
vector<vector<int>> v;
queue<int> q;
 
void solve(){
    while(!q.empty()){
        int pos = q.front();
        q.pop();
        
        for(int i=0;i<v[pos].size();i++){
            int y = v[pos][i];
            if(dp[y] == -1){
                dp[y] = dp[pos]+1;
            }else {
                dp[y] = max(dp[y],dp[pos]+1);
            }
            cnt[y]--;
            if(cnt[y] == 0){
                q.push(y);
            }
        }
    }
}
 
 
int main(){
    
    for(int i=0;i<111111;i++){
        dp[i] = -1;
        cnt[i] = 0;
    }
    
    cin >> n >> m;
    v.resize(n+1);
    
    for(int i=1;i<=n;i++){
        scanf("%d" , &h[i]);
    }
    for(int i=1;i<=m;i++){
        int a,b;
        scanf("%d%d" , &a,&b);
        if(h[a] < h[b]){
            v[b].push_back(a);
            cnt[a]++;
        }else{
            v[a].push_back(b);
            cnt[b]++;
        }
    }
    for(int i=1;i<=n;i++){
        if(cnt[i] == 0){
            q.push(i);
            dp[i] = 1;
        }
    }
    solve();
    for(int i=1;i<=n;i++){
        cout << dp[i] << endl;
    }
 
}