백준 1486 - 등산(C++)

문제 링크입니다. https://www.acmicpc.net/problem/1486

1486번: 등산

다익스트라를 2번 이용해 푸는 문제입니다.

높이를 의미하는 알파벳이 주어지고 N*M이 주어질 때, 세준이가 오를 수 있는 가장 높은 높이를 구하는 문제입니다.
세준이는 (1, 1)에서 시작하고, 높이의 차는 ‘T’이하만 이동할 수 있습니다.

다른 위치로 이동할 때 드는 시간은
1. 현재 위치보다 낮은 곳을 이동할 경우 -> 1
2. 현재 위치보다 높은 곳을 이동 -> (다음 위치 - 현재 위치)^2
2가지 경우로 나누어서 걸립니다.

도착만 한다고 끝나는 것이 아닌, 원래 위치인 (1, 1)로 돌아가야 하기에,  돌아간 시간까지 ‘D’이하로 걸려야 합니다.

따라서, 먼저 (1, 1)에서 출발할 때 다른 높이까지 걸리는 비용, 다른 정점에서 (1, 1)까지 걸리는 비용을 구해서 더해준 뒤,
합이 D이하인 곳을 찾아, 가장 높은 비용을 구하면 됩니다.

여기서 다른 정점에서 출발하여 (1, 1)에서 도착하는 경우를 확인할 때, 모든 정점에서 시작해서 찾는다면, 다익스트라를 많이 돌려야합니다.
하지만, (1, 1)에서 출발한 뒤, 드는 비용을 거꾸로 계산해주면, 다른 정점에서 (1, 1)로 가는 값을 구하는 것과 같습니다.


자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <climits>
#define INF 987654321
#define F first
#define S second

using namespace std;

int N, M, T, D;
int map[26][26];
int Distance[26][26];
int st_dis[26][26], fin_dis[26][26];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
priority_queue<pair<long long, pair<int ,int>>> q;

void reset_distance(){
	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= M; j++){
			Distance[i][j] = INF;
		}
	}
}

void Dijstra(int X, int Y, int way){
	reset_distance();
	Distance[X][Y] = 0;
	q.push({-0, {X, Y}});
	while(!q.empty()){
		int x = q.top().S.F;
		int y = q.top().S.S;
		int cost = -q.top().F;
		q.pop();
		if(Distance[x][y] < cost) continue;
		for(int i = 0; i < 4; i++){
			int xx = x + dx[i];
			int yy = y + dy[i];
			if(xx >= 1 && xx <= N && yy >= 1 && yy <= M){
				if(abs(map[xx][yy] - map[x][y]) > T) continue;
				int n_cost;
				if(way == 0){ //(1,1)애서 올라가는 경우
					if(map[x][y] >= map[xx][yy]){
						n_cost = cost + 1;
					}
					else{
						n_cost = cost + pow(map[x][y] - map[xx][yy], 2);
					}
				}
				if(way == 1){ // 다른 정점에서 내려가는 경우
					if(map[x][y] <= map[xx][yy]){
						n_cost = cost + 1;
					}
					else{
						n_cost = cost + pow(map[x][y] - map[xx][yy], 2);
					}
				}
				if(Distance[xx][yy] > n_cost){
					Distance[xx][yy] = n_cost;
					q.push({-Distance[xx][yy], {xx, yy}});
				}
			}
		}
	}	
}

void solve(){
	//(1,1)에서 시작해 다른 정점으로 갈 때, 걸리는 시간
	Dijstra(1, 1, 0);
	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= M; j++){
			st_dis[i][j] = Distance[i][j];
		}
	}
	//다른 정점에서 시작해 (1,1)로 갈 때, 걸리는 시간
	Dijstra(1, 1, 1);
	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= M; j++){
			fin_dis[i][j] = Distance[i][j];
		}
	}
	int ans = -1;
	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= M; j++){
			if(st_dis[i][j] + fin_dis[i][j] > D) continue;
			ans = max(ans, map[i][j]);
		}
	}
	cout << ans;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M >> T >> D;
	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= M; j++){
			char x;
			cin >> x;
			if(x >= 'a' && x <= 'z') map[i][j] = x - 'a' + 26;
			if(x >= 'A' && x <= 'Z') map[i][j] = x - 'A';
			}
	}
	solve();
	return 0;
}

질문 및 조언은 댓글을 남겨주세요.