[백준/BOJ] 14948 군대탈출하기

문제 : 14948 군대탈출하기

14948번: 군대탈출하기

현재 기준에서 레벨 제한을 높이지 않는 것 먼저 계속 탐색하면 되므로

가중치를 레벨에 두어서 우선순위 큐에 넣고 다익스트라처럼 탐색하면 된다.

 

이때, 도중에 점프를 할 수 있으므로 visited배열을 3차원으로 짜서

건너뛴 적이 없다면 한번 할 수 있게 하고

도착 칸에 도달한 값 중 작은 것을 찾아 출력하면 된다.

---

Code

#include <bits/stdc++.h>
#define ll long long
#define INF 1e9+7
using namespace std;
struct ABC{
    ll x, y, lv, jump; // jump는 건너뛴 횟수
    ABC() {}
    ABC(ll x, ll y, ll lv, ll jump) : x(x), y(y), lv(lv), jump(jump) {}
};
bool operator<(ABC x, ABC y){
    return x.lv>y.lv;
}
ll N, M, arr[105][105], visited[105][105][2]; // 건너뛴적 있는것과 없는것으로 2층
ll dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
priority_queue<ABC> pq;
ll Dijkstra(){
    fill(&visited[0][0][0],&visited[104][104][2],INF);
    visited[0][0][0]=arr[0][0];
    pq.push({0,0,arr[0][0],0});
    while (!pq.empty()){
        ll x=pq.top().x, y=pq.top().y, curr=pq.top().lv, chk=pq.top().jump;
        pq.pop();
        if (curr>visited[x][y][chk])
            continue;
        for (int i=0;i<4;i++){
            ll dx=x+dir[i][0], dy=y+dir[i][1];
            if (dx<0 || dx>=N || dy<0 || dy>=M)
                continue;
            ll next=arr[dx][dy];
            if (max(curr,next)<visited[dx][dy][chk]){
                visited[dx][dy][chk]=max(curr,next);
                pq.push({dx,dy,max(curr,next),chk});
            }
            if (!chk){ // 한번도 건너뛰기를 한적 없다면 2칸전진
                dx+=dir[i][0], dy+=dir[i][1];
                if (dx<0 || dx>=N || dy<0 || dy>=M)
                    continue;
                next=arr[dx][dy];
                if (max(curr,next)<visited[dx][dy][chk+1]){
                    visited[dx][dy][chk+1]=max(curr,next);
                    pq.push({dx,dy,max(curr,next),chk+1});
                }
            }
        }
    }
    return min(visited[N-1][M-1][0],visited[N-1][M-1][1]);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;
    for (int i=0;i<N;i++){
        for (int j=0;j<M;j++){
            cin >> arr[i][j];
        }
    }
    cout << Dijkstra();
    return 0;
}