[C/C++] 백준 - 14699번 : 관악산 등산

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

14699번: 관악산 등산

문제

서울대학교에는 “누가 조국의 미래를 묻거든 고개를 들어 관악을 보게 하라”라는 유명한 문구가 있다. 어느 날 Unused는 Corea에게 조국의 미래를 물었고, Corea는 직접 관악산에 올라가 조국의 미래를 보고 답해 주기로 했다.

관악산의 등산로는 1부터 N까지의 서로 다른 번호가 붙어 있는 N개의 쉼터와 두 쉼터 사이를 오갈 수 있는 M개의 길들로 이루어져 있다. Corea는 지면에서부터 산을 오르는 것은 너무 귀찮다고 생각했기 때문에, 케이블카를 타고 임의의 쉼터에서 내린 다음 등산을 시작하기로 했다. Corea는 항상 더 높은 곳을 지향하기 때문에, 쉼터에 도착하면 그 쉼터와 직접 연결된 더 높은 쉼터로 향하는 길들 중 하나를 골라서 그 길을 따라 이동한다. 만약 그런 길이 없다면 등산을 마친다.

관악산의 쉼터들에는 조국의 미래를 볼 수 있는 전망대가 하나씩 설치되어 있다. Corea는 최대한 많은 쉼터를 방문해서 조국의 미래를 많이 보고 Unused에게 전해 주기로 했다. 관악산의 지도가 주어질 때, Corea가 각각의 쉼터에서 출발해서 산을 오를 때 최대 몇 개의 쉼터를 방문할 수 있는지 구하여라.

 

 

그래프처럼 각 노드 간 연결을 체크해주고, 더 높은 곳을 갈 수 있는 곳은 모두 가보면서 최대 많은 노드를 방문하는 개수를 탐색해야한다.

 

즉, 그래프 이론에 완전탐색을 통해 문제를 해결할 수 있는데 이미 방문을 통해 최대 개수를 파악한 정점에는 방문 정점 개수를 저장해주어 또 다시 탐색하는 경우를 방지해준다.

 

---> 그래프 이론 + 완전 탐색 + 메모이제이션 ; 동적계획법으로 해결 가능

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <set>
#include <map> 
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ENDL cout << endl
#define ll long long	
#define ull unsigned long long
#define INF 987654321
#define Mod 1000000
#define endl '\n'
#define pil pair<int,int>

using namespace std;

int N, M, maxHeight;
int height[5003];
int cache[5003];
vector<int> node[5003];

void input() {
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		cin >> height[i];
		maxHeight = max(maxHeight, height[i]);
	}
	for (int i = 0; i < M; i++) {
		int from, to;
		cin >> from >> to;
		node[from].push_back(to);
		node[to].push_back(from);
	}
}

int path(int index, int h) {
	if (h == maxHeight || node[index].empty()) return 1;
	int& ret = cache[index];
	if (ret != -1) return ret;

	ret = 1;
	for (auto& ptr : node[index]) {
		if (h < height[ptr]) {
			ret = max(ret, path(ptr, height[ptr]) + 1);
		}
	}
	return ret;
}

void solution() {
	memset(cache, -1, sizeof(cache));
	for (int i = 1; i <= N; i++) {
		cout << path(i, height[i]) << endl;
	}
}

int main() {
	fastio;
	input();
	solution();
	
	return 0;
}