[C++/백준] 1486 등산

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

[문제 요약]

1. 높이 차가 T보다 낮아야 이동 가능

2. 높이가 낮거나 같으면 1, 높이가 높으면 (차이)**2 시간이 걸린다. 

3. D 시간만큼 돌아다닐 수 있다. 

4. 갈 수 있는 가장 높은 곳의 높이는?

 

 

[문제 풀이]

일단, 문제를 보면 최단 경로임을 알 수 있었다.

-> 양방향 그래프 + 목적지 없음 + 4방향

 

최단 경로 -> 다익스트라 가능한지 생각해보니 가능 -> 다익스트라 갈김.

 

주의해야 할 거는, 오는 시간과 가는 시간이 다르기 때문에 다익스트라를 두 번 돌려줘야 한다. 

 

(0,0)에서 (5,5)로 갈 때 여러가지 경로로 갈 수 있고 

오는 경로와 가는 경로가 달라도 되기 때문.

 

그래서, visited[25][25][2] 3차원 배열을 만들고 

visited[][][0] : 가는 길, 

visited[][][1] : 오는 길로 구현했다. 

 

 

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<tuple>
#include<math.h>

using namespace std;

int N, M, T, D;
int dy[] = { 1,0,-1,0 };
int dx[] = { 0,1,0,-1 };
int MAP[25][25];
long long visited[25][25][2];

int cal(int nv, int d); // 칸 이동 시 소요 시간 계산
void check_time(int d); // 시작 위치에서 걸리는 최단 시간 계산. 

// 걸리는 시간 계산. 
int cal(int nv, int d) {
	if (d) {
		if (nv < 0)
			return pow(nv, 2);
		return 1;
	}
	else {
		if (nv > 0)
			return pow(nv, 2);
		return 1;
	}

}

void check_time(int d) {

	priority_queue<tuple<long long,int,int>> pq;
	pq.push({ 0,0,0 });

	//dijkstra
	while (!pq.empty()) {
		long long v;
		int y,x;
		tie(v,y,x) = pq.top();
		pq.pop();
		v *= -1;

		if (visited[y][x][d]!=2e9) continue;
		visited[y][x][d] = v;
		
		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			
			if (ny < 0 || nx < 0 || ny >= N || nx >= M) continue;
			if (visited[ny][nx][d]!=2e9) continue;

			// 위상차 구하기
			int nv = MAP[y][x] - MAP[ny][nx];
			// T보다 높으면 안된다. 
			if (abs(nv) > T) continue;
			
			pq.push({ -(v + cal(nv, d)),ny,nx });
		}
	}

}

int main() {
	cin >> N >> M >> T >> D;
	// 입력
	for (int i = 0; i < N;i++) {
		for (int j = 0; j < M; j++) {
			char n;
			cin >> n;
			MAP[i][j] = n >= 'a' ? int(n) - int('a') + 26 : int(n) - int('A');
		}
	}

	//최단 시간 구함 ->  2e9로 초기화
	fill(&visited[0][0][0], &visited[0][0][0] + 25 * 25 * 2, 2e9);

	// 가는 길 Dijk
	check_time(0);
	// 오는 길 Dijk
	check_time(1);
	
	int ans = 0;

	//visited[][][0], visited[][][1]에 있는 시간을 더해서 갈 수 있는 최대 높이 찾기
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			// 가는 시간 + 오는 시간 <= 가능한 시간이면
			if (visited[i][j][0] + visited[i][j][1] <= D) {
				ans = max(ans, MAP[i][j]);
			}
		}
	}

	cout << ans;
}