boj 14699 관악산 등산

게을러져서 문제도 많이 안풀고 풀이 남기는 것도 귀찮았는데 그래도 주1회 정도는 포스팅을 하려고 다시 마음을 먹었다.

서울대 프로그래밍 콘테스트 문제를 하나씩 풀어나가고 있다. 

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

문제를 읽고 처음 든 순간은 최단거리네? 최단거리 알고리즘 중에 아무꺼나 하나 골라 쓰자였다. 그 생각에 사로잡혀 문제 조건도 확인안하고 다익스트라를 n번 돌리는걸로 답을 구해 시간초과 ... 와샬플로이드써서 시간초과 ....

그렇게 두번 실패를 하고 찬찬히 다시 문제를 읽어보니 간단한 dp 문제였다.  코딩 테스트 같은걸 볼때 쉬운 문제라도 이런 실수를 해버리면 시간안에 못풀수있겠다는 생각이 든다. 경각심을 가져야겠다.

풀이 :  일단 더 위쪽 쉼터에서 아래로 내려가는 경우가 없으므로 양방향이 아닌 단방향(저 -> 고)으로 그래프를 만든다. 그 후에 dfs로 탐색을 하는데 현재 쉼터 s에서 들릴 수 있는 최대 쉼터 갯수 d(s)는 max( d(s에서 갈 수 있는 모든 쉼터)  + 1) 이다.  재귀적인 속성을 가지므로 재귀함수로 작성을 하면 간단하다. 또한 d(s)는 중복 호출이 많이 되므로 메모이제션을 해서 중복 계산을 막는다.

소스코드  

#include <iostream>

#include <vector>

#include <cstdio>

#include <algorithm>

using namespace std;

int a, b, V, E;

const int MAX_V = 5001;

const int INF = 987654320;

vector<pair<int, int>>adj[MAX_V];

vector<int> cache(MAX_V, -1);

int dp(int s) {

int &ret = cache[s];

if (ret != -1) return ret;

int res = 1;

for (int i = 0; i < adj[s].size(); i++) {

res = max(res, dp(adj[s][i].first) + 1);

}

return ret = res;

}

int main() {

cin >> V >> E;

for (int i = 0; i<E; i++) {

scanf("%d%d", &a, &b);

a--; b--;

//더 위에 있는 쉼터만 연결함.

if (height[a] < height[b]) adj[a].push_back(pair<int, int>(b, 1));

else if (height[a] > height[b]) adj[b].push_back(pair<int, int>(a, 1));

}

int res = 0;

for (int j = 0; j < V; j++) {

cout << dp(j) << endl;

}

}