[BOJ 14699 // C++] 관악산 등산

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 14699번 문제인 관악산 등산이다.
문제는 아래 링크를 확인하자.

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

14699번: 관악산 등산

각 쉼터의 가능한 경로의 길이의 최댓값은 연결된 길을 따라 더 높은 다음 쉼터로 올라갔을 때의 (각 쉼터에서의 가능한 경로의 길이 최댓값+1)들 중 최댓값이 된다. 이것을 쉽게 구하는 방법으로 위상정렬이 있다.

 

주어지는 쉼터들을 노드로, 산책로를 더 높은 위치의 심터에서 낮은 위치의 쉼터로 향하는 directed edge로 표현하면 DAG를 하나 얻을 수 있다. 이 그래프에서 위상정렬 순으로 각 노드에서 출발해 거칠 수 있는 쉼터의 개수의 최댓값을 갱신해나가자.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int N, M;
vector<int> G[5001];
int H[5001];
int indegree[5001];
queue<int> que;
int ans[5001];

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

	cin >> N >> M;
	for (int i = 1; i <= N; i++)cin >> H[i];
	while (M--) {
		int x, y; cin >> x >> y;
		if (H[x] < H[y]) G[y].emplace_back(x), indegree[x]++;
		else G[x].emplace_back(y), indegree[y]++;
	}

	for (int i = 1; i <= N; i++) {
		if (indegree[i] == 0) que.push(i);
	}

	while (!que.empty()) {
		int x = que.front(); que.pop();
		ans[x]++;
		for (auto node : G[x]) {
			ans[node] = max(ans[node], ans[x]);
			indegree[node]--;
			if (indegree[node] == 0) que.push(node);
		}
	}

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