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

www.acmicpc.net/problem/4485

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

bfs로 풀어도 되지만 다익스트라를 사용해서 풀었다.

다익스트라 사용시 우선순위 큐를 사용함.

다익스트라 구현방법 외우자..ㅠ

#include <stdio.h>
#include <queue>
#define INF 1e9
using namespace std;

int n;
int cave[125][125];
int dis[125][125];

struct s
{

    int row, col, cost;
};

struct cmp
{

    bool operator()(const s &t1, const s &t2)
    {
        if (t1.cost == t2.cost)
        {
            return t1.row > t2.row;
        }
        return t1.cost > t2.cost;
    }
};

priority_queue<s, vector<s>, cmp> pq;

int Dijkstra(void)
{

    int dr[4] = {0, 0, -1, 1};
    int dc[4] = {1, -1, 0, 0};
    dis[0][0] = cave[0][0];
    pq.push({0, 0, dis[0][0]});

    while (!pq.empty())
    {
        s cur = pq.top();
        pq.pop();

        for (int i = 0; i < 4; i++)
        {
            int nr = cur.row + dr[i];
            int nc = cur.col + dc[i];

            if (nr < 0 || nc < 0 || nr > n - 1 || nc > n - 1)
            {
                continue;
            }

            if (dis[nr][nc] > cur.cost + cave[nr][nc])
            {

                dis[nr][nc] = cur.cost + cave[nr][nc];
                pq.push({nr, nc, dis[nr][nc]});
            }
        }
    }

    return dis[n - 1][n - 1];
}

int main(void)
{
    int idx = 1;
    while (1)
    {
        scanf("%d", &n);
        if (n == 0)
        {
            break;
        }

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                dis[i][j] = INF;
            }
        }

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                scanf("%d", &cave[i][j]);
            }
        }

        int res = Dijkstra();
        printf("Problem %d: %d\n", idx, res);
        idx++;
    }

    return 0;
}