백준 문제 링크 : 1486번: 등산 (acmicpc.net)
백준 1486번 문제 사진
문제 요약
입력 값 : n,m(산의 세로, 가로), t(한번에 이동할 수 있는 높이 차이), d(제한 시간)
- 세준이는 0-51의 높이를 지닌 산을 오르려고 한다.
- 세준이는 항상 (0,0) 좌표에서 출발한다.
- 현재 위치에서 높이가 낮은 곳이나 같은 곳으로 이동한다면 시간은 1초가 걸린다. 하지만 높은 곳으로 이동한다면 두 위치의 높이의 차이의 제곱만큼 시간이 걸린다.
문제 풀이 과정
문제를 한 줄로 요약하자면 세준이가 제한 시간 내에 (N x M) 크기의 산에서 다녀올 수 있는 최대 높이를 구하는 문제입니다.
이때 높이 차이는 t를 넘지 말아야 하죠. 그리고 등산을 한 후 다시 호텔로 돌아와야 하기 때문에 돌아오는 시간을 고려하여야만 합니다.
일단 각 정점의 최단 경로를 찾아야 하는 문제이기 때문에 다익스트라 알고리즘을 사용했습니다.
제한 시간 내에 갈 수 있는 장소의 도달 시간을 다익스트라 알고리즘을 통해서 map_distance 배열에 먼저 저장해둔 후 돌아올 때 걸리는 시간을 연산하여 map_return 배열에 저장하였죠.
이후 두 시간의 합이 제한 시간 이내인 높이를 선별하고 그중 최고 높이를 출력하도록 만들었습니다.
#include <iostream>
#include <queue>
#include <cmath>
#define MAX 1e9
using namespace std;
//방향 선언
pair<int,int> direction[4] = {
{1,0},
{-1,0},
{0,1},
{0,-1}
};
//사용 변수 선언
int n,m,t,d;
//배열 공간 선언
int map[25][25] = {0};
//배열 거리 선언
int map_distance[25][25] ={};
int map_return[25][25] = {};
//다익스트라 알고리즘
void dijkstra(int target_map[25][25],int x,int y,bool is_back = false){
target_map[x][y] = 0;
priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>>> queue;
queue.push({0,{x,y}});
while (!queue.empty()) {
int cur_distance = queue.top().first;
int cur_x = queue.top().second.first;
int cur_y = queue.top().second.second;
queue.pop();
if (cur_distance > d) continue;
if (target_map[cur_x][cur_y] < cur_distance) continue;
for (int i = 0;i < 4; i++) {
int next_x = cur_x + direction[i].first;
int next_y = cur_y + direction[i].second;
if (next_x >= n || next_x < 0||next_y >= m || next_y < 0) continue;
int sub = map[next_x][next_y] - map[cur_x][cur_y];
if (abs(sub) > t ) continue;
int distance = target_map[cur_x][cur_y];
if (!is_back) {
if (sub <= 0) {distance += 1;}
else {distance += pow(abs(sub),2);}
}
else{
if (sub >= 0) {distance += 1;}
else {distance += pow(abs(sub),2);}
}
if (distance < target_map[next_x][next_y]) {
target_map[next_x][next_y] = distance;
queue.push({distance,{next_x,next_y}});
}
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
//배열 초기화
for (int i = 0; i < 25; i++)
for (int j = 0; j < 25; j++)
map_distance[i][j] = MAX;
for (int i = 0; i < 25; i++)
for (int j = 0; j < 25; j++)
map_return[i][j] = MAX;
//변수 입력
cin >> n >> m >> t >> d;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
char c;
cin >> c;
if (c >= 'A' && 'Z' >= c) {
map[i][j] = (int)c - 65 + 0;
}
else {
map[i][j] = (int)c - 97 + 26;
}
}
}
//등산로 탐색
dijkstra(map_distance,0,0);
dijkstra(map_return,0,0,true);
//탐색 등산로의 합을 구한 후 갈 수 있는 최대 높이를 구함
int max_height = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int total_dist = map_distance[i][j] + map_return[i][j];
if (total_dist <= d) {
max_height = max(max_height,map[i][j]);
}
}
}
//최대 높이 출력
cout << max_height << endl;
return 0;
}코드는 위와 같이 작성하였습니다. 다익스트라 알고리즘에 is_back이라는 매개 변수를 추가하여 false일 때에는 가는 거리 true일 때에는 오는 거리를 계산하도록 하였죠. 이상입니다.
다익스트라 알고리즘을 사용한 다른 문제의 경우 아래 카테고리에서 찾아보실 수 있습니다.