BOJ : www.acmicpc.net/problem/1486
1486번: 등산
첫째 줄에 산의 세로크기 N과 가로크기 M 그리고, T와 D가 주어진다. N과 M은 25보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 지도가 주어진다. T는 52보다 작거나 같은 자연수이고, D는 1,000
www.acmicpc.net
문제
세준이가 가려고하는 산의 지도가 입력으로 주어진다. 산의 지도를 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();
}
'algorithm > BOJ' 카테고리의 다른 글
| [JS & Stack] 10828번: 스택 (0) | 2023.07.19 |
|---|---|
| BOJ 2273번 줄 서기 (0) | 2021.04.17 |
| BOJ 3584번 가장 가까운 공통 조상 (0) | 2021.03.31 |
| BOJ 1103번 게임 (0) | 2021.03.16 |
| BOJ 2194번 유닛 이동시키기 C++ (0) | 2020.07.05 |
