[4485번] 녹색 옷 입은 애가 젤다지?

문제 출처 :

https://www.acmicpc.net/problem/4485

알고리즘 분석 :

문제 해결에 필요한 사항

1. 우선순위 큐 다익스트라

이 문제는 첫 시작점에서 끝점으로의 하나의 최단거리를 구하면 되기에 BFS 방식처럼 우선순위 큐 다익스트라를 돌리면 해결 할 수 있다.

생각외로 조건이 많이 없는 문제이므로 간단히 해결 할 수 있다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <queue>
#include <functional>
 
#define INF 987654321
 
using namespace std;
 
typedef pair<int, int> pii;
 
int adj[130][130];
int dist[130][130];
 
int main()
{
    int tCase = 1;
    while (tCase++)
    {
        int n;
        scanf("%d", &n);
 
        if (!n)
            break;
 
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
            {
                dist[i][j] = INF;
                scanf("%d", &adj[i][j]);
            }
        
        queue<pair<int,pii>> pq;
 
        dist[0][0] = adj[0][0];
        pq.push({ dist[0][0], pii(0, 0) });
    
 
        while (!pq.empty())
        {
            int cost = pq.front().first;
            int y = pq.front().second.first;
            int x = pq.front().second.second;
 
            pq.pop();
 
            if (dist[y][x] < cost)
                continue;
        
            if (y + 1 < n &&  dist[y + 1][x] > cost + adj[y + 1][x])
            {
                dist[y + 1][x] = cost + adj[y + 1][x];
                pq.push({ dist[y + 1][x], pii(y + 1, x) });
            }
 
            if (y - 1 >= 0 && dist[y - 1][x] > cost + adj[y - 1][x])
            {
                dist[y - 1][x] = cost + adj[y - 1][x];
                pq.push({ dist[y - 1][x], pii(y - 1, x) });
            }
 
            if (x + 1 < n &&dist[y][x + 1] > cost + adj[y][x + 1])
            {
                dist[y][x + 1] = cost + adj[y][x + 1];
                pq.push({ dist[y][x + 1], pii(y, x + 1) });
            }
 
            if (x - 1 >= 0 && dist[y][x - 1] > cost + adj[y][x - 1])
            {
                dist[y][x - 1] = cost + adj[y][x - 1];
                pq.push({ dist[y][x - 1], pii(y, x - 1) });
            }
        }
 
        
        printf("Problem %d: %d\n", tCase - 1, dist[n - 1][n - 1]);
    }
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>