[백준]소가 길을 건너간 이유 7(14461)

문제 링크 : [백준]소가 길을 건너간 이유 7(14461)

문제 설명

N * N 행렬이 주어지고, 각 칸에는 풀의 양이 주어집니다.
소는 (1,1)에서 출발하여, (N,N)까지 이동해야 합니다.
각 칸을 이동 할 때는 T초가 걸리며, 소가 세칸을 이동한 후에는 그 칸의 풀을 먹어야 합니다.
소가 도착하는데 걸리는 최소 시간을 구하세요.

입력

N(행렬의 크기, 1 <= N <= 100)
T(한 칸을 이동하는데 걸리는 시간, 0 <= T <= 1,000,000)
P_ij(각 칸에 있는 풀의 양, 1 <= P_ij <= 100,000)

4 2
30 92 36 10
38 85 60 16
41 13 5 68
20 97 13 80

출력

31

카테고리

#다익스트라

시간 복잡도 상한

O(N⁴)

해결 방법

1. 다익스트라를 이용한 최단 거리를 구하면 됩니다.
2. 단, 비용을 구하는 방법이 [기존 비용] + T + [풀을 먹고난 후, 이동 횟수가 3 ? 도착한 곳의 풀 : 0]을 한 값이 됩니다.
3. 따라서 우선순위 큐에 넣는 일반적인 정보에 추가적으로 풀을 먹고난 후 이동 거리를 같이 넣고, 다음에 큐를 넣을 때, 2번 식을 따라 큐에 넣습니다.

시간복잡도

O(N² * logN²)

코드

#include<cstdio>
#include<queue>
#include<algorithm>
#define X second.second.first
#define Y second.second.second
#define C second.first
using namespace std;
typedef long long L;
typedef pair<L,pair<int,pair<int,int>>>P;
int n,t,d[100][100],i,j,o[4][2]={{1,0},{0,1},{-1,0},{0,-1}},v[100][100][3];
priority_queue<P,vector<P>,greater<P>>q;
int main(){
    scanf("%d%d",&n,&t);
    for(i=0;i<n;i++)for(j=0;j<n;j++)scanf("%d",d[i]+j);
    q.push({0,{0,{0,0}}});
    while(!q.empty()){
        P c=q.top();q.pop();
        if(v[c.X][c.Y][c.C])continue;
        v[c.X][c.Y][c.C]=1;
        if(c.X==n-1&&c.Y==n-1){
            printf("%lld",c.first);
            break;
        }
        for(i=0;i<4;i++){
            int nx=c.X+o[i][0],ny=c.Y+o[i][1];
            if(nx>=0&&ny>=0&&nx<n&&ny<n){
                if(c.C==2)q.push({c.first+t+d[nx][ny],{0,{nx,ny}}});
                else q.push({c.first+t,{c.C+1,{nx,ny}}});
            }
        }
    }
}