[SWEA] 1249번 보급로

1249 보급로

풀이)

다익스트라를 이용한다면 쉽게 풀 수 있는 문제이다.

코드)

#include <stdio.h>
#include <queue>
#include <algorithm>
using namespace std;
 
#define INF 999999999
int n;
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
int map[100][100];
int dist[100][100];
 
int Dijkstra() {
    for (int i = 0; i < n; i++) {
        fill(dist[i], dist[i] + n, INF);
    }
    
    priority_queue <pair<int,pair<int, int>>> qu;
    qu.push({ 0,{0,0} });
    dist[0][0] = 0;
    while (!qu.empty())
    {
        int cost = -qu.top().first;
        int y = qu.top().second.first;    
        int x = qu.top().second.second;
        qu.pop();
        if (dist[y][x] < cost) continue;
        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (ny >= 0 && ny < n && nx >= 0 && nx < n) {
                int next_cost = cost + map[ny][nx];
                if (dist[ny][nx] > next_cost) {
                    dist[ny][nx] = next_cost;
                    qu.push({ -next_cost,{ny,nx} });
                }
            }
        }
    }
 
    return dist[n - 1][n - 1];
}
 
int main() {
    //freopen("input.txt", "r", stdin);
    int T = 0;
    scanf("%d", &T);
    for (int test_case = 1; test_case <= T; test_case++) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                scanf("%1d", &map[i][j]);
            }
        }
        printf("#%d %d\n", test_case, Dijkstra());
    }
    return 0;
}