1249 보급로

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD

지도의 왼쪽 맨 위에서 오른쪽 맨 아래로 이동하는 최단 거리를 구하는 문제이다. 오른쪽이나 아래로만 이동이 가능하면 다이나믹으로 해결가능하지만 상하좌우로 이동 가능하기 때문에 다익스트라로 해결한다.

#include <cstdio>
#include <queue>
#define INF 987654321
using namespace std;
 
int t,n,map[100][100],dist[100][100];
int dx[4]={0,0,-1,1},dy[4]={-1,1,0,0};
 
int dijkstra()
{
    priority_queue<pair<int,pair<int,int>>> pq;
    pq.push({0,{0,0}});
    while(!pq.empty())
    {
        int cost=-pq.top().first;
        int x=pq.top().second.first;
        int y=pq.top().second.second;
        pq.pop();
        if(dist[x][y]<cost) continue;
        for(int i=0;i<4;i++)
        {
            int nx=x+dx[i],ny=y+dy[i];
            if(nx<0 || nx>=n || ny<0 || ny>=n) continue;
            int ndist=cost+map[nx][ny];
            if(dist[nx][ny]>ndist)
            {
                dist[nx][ny]=ndist;
                pq.push({-ndist,{nx,ny}});
            }
        }
    }
    return dist[n-1][n-1];
}
 
int main()
{
    scanf("%d",&t);
    for(int k=1;k<=t;k++)
    {
        scanf("%d",&n);
        for(int i=0;i<n;i++) for(int j=0;j<n;j++)
            scanf("%1d",&map[i][j]),dist[i][j]=INF;
        printf("#%d %d\n",k,dijkstra());
    }
    return 0;
}