BOJ 14699

30 Jan 2020 • ProblemSolving

관악산 등산

문제출처

1.설계(X)

  • 문제 해석

    • N개의 쉼터와 M개의 길이 있을 때, 각각 쉼터에서 산을 오를 때 최대로 지나갈 수 있는 쉼터의 개수를 출력하는 문제입니다.
    • N <= 5000, M <= 100,000
    • 사이클이 없고, 쉼터를 연결하는 길이 여러 개 있을 수도 있습니다.

  • 설계

    • 각 쉼터에서 다른 쉼터로 가는 방향은 높이 차로 결정합니다. 높이가 높은 쪽으로 가게 해야 합니다.
    • 저는 이후, 각 쉼터에 대해서 높이차가 작은 순으로 정렬을 하여 dfs를 이용하였지만 WA가 나왔습니다.
    • 다른 분들의 코드를 참조해보니 dp 또는 위상정렬을 이용하였습니다.

2.구현(X)

  • 코드1(위상정렬)
#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;
#define MAXN 5000
int height[MAXN];

vector<int> adj[MAXN];

int N, M;

int indegree[MAXN];
bool visited[MAXN];
int ans[MAXN];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> height[i];
	}
	for (int i = 0; i < M; i++) {
		int u, v;
		cin >> u >> v;
		u--;
		v--;
		if (height[u] < height[v]) {
			indegree[u]++;
			adj[v].push_back(u);
		}
		else if (height[u] > height[v]){
			indegree[v]++;
			adj[u].push_back(v);
		}
	}
	queue<int> q;
	for (int i = 0; i < N; i++) {
		if (indegree[i] == 0) q.push(i);
		ans[i] = 1;
	}
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		for (int i = 0; i < adj[cur].size(); i++) {
			int next = adj[cur][i];
			ans[next] = max(ans[next], ans[cur] + 1);
			indegree[next]--;
			if (indegree[next] == 0) q.push(next);
		}
	}
	for (int i = 0; i < N; i++) {
		cout << ans[i] << "\n";
	}
	return 0;
}
  • 코드2(dp)
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;
#define MAXN 5000
int height[MAXN];

vector<int> adj[MAXN];

int N, M;
int cache[MAXN];

int dp(int cur) {
	int& ret = cache[cur];
	if (ret != -1) return ret;
	ret = 1;
	for (int i = 0; i < adj[cur].size(); i++) {
		ret = max(ret, dp(adj[cur][i]) + 1);
	}
	return ret;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> M;
	memset(cache, -1, sizeof(cache));
	for (int i = 0; i < N; i++) {
		cin >> height[i];
	}
	for (int i = 0; i < M; i++) {
		int u, v;
		cin >> u >> v;
		u--;
		v--;
		if (height[u] < height[v]) {
			adj[u].push_back(v);
		}
		else if (height[u] > height[v]) {
			adj[v].push_back(u);
		}
	}
	
	for (int i = 0; i < N; i++) {
		cout << dp(i) <<"\n";
	}
	
	return 0;
}

  • 디버깅

    • 위상정렬로 구현을 할 때에는 높은 곳에서 낮은 곳으로 이동하게 방향을 설정해서 각 쉼터의 최대값을 갱신하도록 하였습니다.
    • 공개코드로 된 lsn1106님의 코드를 참조해서 dp를 구현하였습니다.

  • 제출결과

3.마무리

  • dp는 구현은 단순한데 이를 dp로 이용하겠다라는 생각을 하기가 어려운 것 같습니다. dp관련 문제를 더 풀어봐야 알 것 같습니다.
 BOJ

Related Posts