BOJ 1486번 등산

BOJ : www.acmicpc.net/problem/1486

1486번: 등산

문제

세준이가 가려고하는 산의 지도가 입력으로 주어진다. 산의 지도를 M이라고 했을 때, M[i][j]는 (i,j)의 높이가 M[i][j]라는 것을 의미한다. 그 값이 'A'-'Z'일 때는 0-25를 뜻하는 것이고, 'a'-'z'일 때는, 26-51을 뜻한다.

세준이의 호텔은 (0,0)에 있다. 그리고, 세준이는 지금 위치에서 바로 인접한 정수 좌표 중 높이의 차이가 T보다 크지 않은 곳으로만 다닐 수 있다.

만약 세준이가 현재 위치에서 높이가 낮은 곳이나 같은 곳으로 이동한다면 시간은 1초가 걸린다. 하지만 높은 곳으로 이동한다면 두 위치의 높이의 차이의 제곱만큼 시간이 걸린다. 예를 들어 높이가 5에서 높이가 9인 곳으로 간다면, 시간은 (5-9)2=16초가 걸린다. 하지만, 높이가 9인 곳에서 5인 곳으로 간다면 시간은 1초가 걸린다.

산의 지도와, T, 그리고 어두워지는 시간 D가 주어졌을 때, 세준이가 D보다 크지 않은 시간 동안 올라갈 수 있는 최대 높이를 구하는 프로그램을 작성하시오.(세준이는 호텔에서 출발해서 호텔로 돌아와야 한다.)

 

입력

첫째 줄에 산의 세로크기 N과 가로크기 M 그리고, T와 D가 주어진다. N과 M은 25보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 지도가 주어진다. T는 52보다 작거나 같은 자연수이고, D는 1,000,000보다 작거나 같은 자연수이다.

 

출력

첫째 줄에 세준이가 갈 수 있는 가장 높은 곳의 높이를 출력한다.

 

풀이

문제에 접근해보면 (0.0)에서 출발해서 어느 지점 (y,x) 을 지나 다시 제자리(0.0) 으로 돌아오는 문제다

그 과정에서 y,x -> yy,xx 로 이동할 때

y,x 가 yy,xx 보다 같거나 크면 시간이 +1

y,x 가 yy,xx 보다 작으면 그 차이만큼 제곱한 시간을 더해주게 된다

결국 (0,0)에서 (y,x)로 이동하는데 걸리는 시간D1 과 (y,x)에서 (0,0)으로 이동하는데 걸리는 시간 D2

D1 + D2가 D보다 작은 모든 경우 중에서 가장 큰 좌표의 높이를 구하는 문제이다

 

결론 => 

(0,0)으로부터 모든 좌표로의 최소시간

(y,x)으로부터 모든 좌표로의 최소시간

다익스트라를 사용하여 문제를 해결

 

minHeap을 사용해야하는데 계속 maxHeap을 사용하는 실수를 하네..?

 

#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <cmath>
using namespace std;

struct pii{
	int time, y, x;
};

struct compare {
	bool operator()(pii& a, pii& b) {
		return a.time > b.time;
	}
};

#define INF 987654321
int my[4] = { -1,1,0,0 };
int mx[4] = { 0,0,1,-1 };
string arra[30];
int arr[30][30];
int dp[30][30][30][30];
int N, M, T, D;

void getDijkstra(int sy, int sx) {

	priority_queue<pii, vector<pii>, compare> pq;
	pq.push({ 0, sy, sx });
	dp[sy][sx][sy][sx] = 0;
	while (!pq.empty()) {
		int y = pq.top().y;
		int x = pq.top().x;
		int time = pq.top().time;
		pq.pop();

		if (dp[sy][sx][y][x] < time) continue;

		for (int i = 0; i < 4; i++) {
			int yy = y + my[i];
			int xx = x + mx[i];
			if (yy < 0 || xx < 0 || yy >= N || xx >= M) continue;

			if (abs(arr[y][x] - arr[yy][xx]) > T) continue;
			
			int nextTime;
			if (arr[y][x] >= arr[yy][xx]) {
				nextTime = time + 1;
			}
			else {
				nextTime = pow(abs(arr[y][x] - arr[yy][xx]), 2) + time;
			}

			if (nextTime < dp[sy][sx][yy][xx]) {
				dp[sy][sx][yy][xx] = nextTime;
				pq.push({ nextTime, yy, xx });
			}
		}
	}
}

int dijkstra() {

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			for (int a = 0; a < N; a++) {
				for (int b = 0; b < M; b++) {
					dp[i][j][a][b] = INF;
				}
			}
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			getDijkstra(i, j);
		}
	}

	int answer = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (dp[0][0][i][j] == INF || dp[i][j][0][0] == INF) continue;
			int calTime = dp[0][0][i][j] + dp[i][j][0][0];
			if (calTime <= D) {
				answer = max(answer, arr[i][j]);
			}
		}
	}

	return answer;
}

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

	cin >> N >> M >> T >> D;
	for (int i = 0; i < N; i++) {
		cin >> arra[i];
		for (int j = 0; j < M; j++) {
			if (arra[i][j] >= 'A' && arra[i][j] <= 'Z') arr[i][j] = arra[i][j] - 'A';
			else arr[i][j] = arra[i][j] - 'a' + 26;
		}
	}

	cout << dijkstra();
}