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

[적용한 알고리즘]

다익스트라 알고리즘

 

[아이디어]

다익스트라의 기본적인 문항이라고 한다.

다만 각 칸 자체가 cost 로 봐줘야한다.

 

[생각의 흐름 / 절차] 

내용

 

[교훈]

근데 저 알고리즘인지 몰랐다면, 아직 허접인 나는 이게 

DP 문제인 줄 알았을 것 같다. 어디서 차이를 알아야하는 거지?

 

<코드>

#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const int MAX = 126;
const int INF = 1000000000;

int dirx[] = {-1, 1, 0, 0};
int diry[] = {0, 0 ,1, -1};
int n;
struct Ver{
    int x, y, dist;
    bool operator < (const Ver &v) const{
        return dist > v.dist;
    }
};

bool inMap(int x, int y){
    if (1 <= x && x <= n && 1 <= y && y <= n) return true;
    return false;
}

int main(){
    int t = 0;
    while (true){
        t++;
        bool visited[MAX][MAX] = { 0 };
        int map[MAX][MAX] = { 0 };
        int dist[MAX][MAX] = { 0 };

        scanf("%d", &n);
        if (n == 0) return 0;
        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= n; j++){
                scanf("%d", &map[i][j]);
                dist[i][j] = INF;
            }
        }

        dist[1][1] = map[1][1];
        priority_queue<Ver> PQ;
        PQ.push({1, 1, dist[1][1]});

        while (!PQ.empty()){
            Ver cur;

            do {
                cur = PQ.top();
                PQ.pop();
            } while (!PQ.empty() && visited[cur.x][cur.y]);

            if (visited[cur.x][cur.y]) break;
            visited[cur.x][cur.y] = true;

            for (int k = 0; k < 4; k++){
                int nx = cur.x + dirx[k];
                int ny = cur.y + diry[k];

                if (inMap(nx, ny) && !visited[nx][ny]){
                    if (dist[nx][ny] > dist[cur.x][cur.y] + map[nx][ny]){
                        dist[nx][ny] = dist[cur.x][cur.y] + map[nx][ny];
                        PQ.push({nx, ny, dist[nx][ny]});
                    }
                }
            }
        }
        printf("Problem %d: %d\n", t, dist[n][n]);
    }
}