[백준 1486] 등산 (C++)

1486번: 등산

 

다익스트라를 사용해서 풀었다.

 

• 가로와 세로의 최대 길이가 26으로 짧다.
• 시작점으로 되돌아와야 한다.

1. 모든 점에 대해서 원점으로 돌아오는 최단거리를 구한다.

 

우선순위 큐에 들어갈 수 없는 정점은 아래와 같다.

1. 현재 위치의 높이와 다음 위치의 높이 차이가 T보다 크다

2. 다음 정점에 대해서 이미 최단거리가 구해져 있다.

3. 다음 정점으로 가는 거리가 D보다 크다.

4. 다음 정점이 Map을 벗어난다.

 

위 4가지의 경우에 대해서 continue를 사용해, 우선순위큐에 정보를 넣지 않고 넘겼다.

만약 0, 0에 도달하면 시작점에서 0,0으로 가는 최단거리를 저장해주고 현재 다익스트라를 빠져나간다.

 

 

2. 원점에서 시작해서 도달할 수 있는 가장 높은 정점을 찾는다.

다익스트라의 우선순위 큐에 정보가 입력되는 조건은 똑같다. 따라서 is_climb 매개변수를 설정해서 현재 다익스트라가 원점으로 돌아가는 중인지, 최대 높이 산을 찾는 중인지 구분하도록 했다.

 

추가된 조건

1. 만약 (현재 최단거리 + 현재 정점에서 원점으로 돌아가는 거리)가 D보다 크면 continue;
2. 1번 조건에 걸리지 않고, 현재 정점의 높이가 현재까지 구한 최대 높이보다 크다면, 최대 높이를 갱신해준다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstring>
#define fasti ios_base::sync_with_stdio(false); cin.tie(0);
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 1e9+7
#define pii pair<int, int>
 
typedef long long ll;
// typedef pair<int, int> pii;
 
using namespace std;
 
int N, M, T, D;
int Map[27][27];
int preset[27][27];
int max_height;
int dr[4] = {0, 0, 1, -1}, dc[4] = {1, -1, 0, 0};
 
struct W{
    int r, c, d;
};
 
struct cmp{
    bool operator()(const W &a, const W &b){
        return a.d > b.d;
    }
};
 
void input(){
    cin >> N >> M >> T >> D;
    
    string str;
    for(int i = 0; i < N; i++){
        cin >> str;
        for(int j = 0; j < M; j++){
            if(islower(str[j])){
                Map[i][j] = str[j] - 'a' + 26;
            }
            else{
                Map[i][j] = str[j] - 'A';
            }
        }
    }
    max_height = Map[0][0];
    
    for(int r = 0; r < 27; r++){
        for(int c = 0; c < 27; c++){
            preset[r][c] = INF;
        }
    }
}
 
void dijkstra(int r, int c, bool is_climb){
    int temp[27][27];
    for(int i = 0; i < 27; i++){
        for(int j = 0; j < 27; j++){
            temp[i][j] = INF;
        }
    }
    priority_queue<W, vector<W>, cmp> pq;
    pq.push({r, c, 0});
    
    while(!pq.empty()){
        W now = pq.top();
        pq.pop();
        
        if(!is_climb && now.r == 0 && now.c == 0){
            preset[r][c] = now.d;
            return;
        }
        
        if(is_climb && now.d + preset[now.r][now.c] > D) continue;
        if(is_climb && Map[now.r][now.c] > max_height) max_height = Map[now.r][now.c];
        
        for(int k = 0; k < 4; k++){
            int nr = now.r + dr[k];
            int nc = now.c + dc[k];
            int next_d = now.d;
            if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
            if(abs(Map[nr][nc] - Map[now.r][now.c]) > T) continue;
            
            if(Map[nr][nc] > Map[now.r][now.c]){
                next_d += pow(Map[nr][nc] - Map[now.r][now.c], 2);
            }
            else next_d += 1;
            
            if(next_d >= temp[nr][nc] || next_d > D) continue;
            temp[nr][nc] = next_d;
            pq.push({nr, nc, next_d});
        }
    }
}
 
void solve(){
    for(int r = 0; r < N; r++){
        for(int c = 0; c < M; c++){
            dijkstra(r, c, false);
        }
    }
    
    dijkstra(0, 0, true);
    
    cout << max_height;
}
 
int main(){
    fastio
    input();
    solve();
    
    return 0;
}