문제

문제 링크

다익스트라를 구현해보는 문제다.

근데 처음에 좀 당황스러웠던게
기존에는 1 2 10 처럼 1->2로 가는데 10 cost가 듭니다. 형태로 다익스트라를 구현했었다.

문제는 0,0 에서 n-1,n-1로 가는데 거리를 구하는 것이었다.

그래서 위 그래프에서는 9개의 노드가 존재하고 각 노드로 이동하는데 걸리는 비용이라고 생각하여 접근하였다.

또한 다익스트라는 최소 비용인 간선들을 계속해서 뽑아내야해서 우선순위 큐가 사용된다.
python에서는 heap으로 사용했는데 c++은 queue와 비슷하게 priority_queue가 존재했다.

맴버 함수로 front 대신 top을 사용한다.(위에만 접근하므로)

또한 default로 최대 힙으로 되어있어 최소 힙을 사용하고 싶으면 -을 붙여서 사용하면 될듯하다.

code

/**
 * 백준 4485
 * 다익스트라
 * 최소 스패닝 트리
*/
#include <bits/stdc++.h>
#define INF 1e9
using namespace std;

int n;
vector<vector<int>> graph;
vector<vector<int>> d;

int dy[]={-1,0,1,0};
int dx[]={0,1,0,-1};

void dijkstra(){
    priority_queue<vector<int>> que;
    // cost,now_y,now_x
    int sY=0,sX=0;
    que.push({-graph[sY][sX],sY,sX});
    d[sY][sX]=graph[sY][sX];

    while(!que.empty()){
        vector<int> now = que.top();
        que.pop();
        int nC=-now[0];
        int nY=now[1];
        int nX=now[2];

        // 현재거리가 더 짧다면 검사 x
        if(d[nY][nX]<nC){continue;}

        // 인접 노드 거리 체크
        for(int i=0;i<4;i++){
            int mY=nY+dy[i];
            int mX=nX+dx[i];

            // 범위
            if(mY<0 || mY>=n || mX<0 || mX>=n) continue;

            // 현재 거리보다 경유하는게 더짧다면 갱신
            int newDist=d[nY][nX]+graph[mY][mX];
            if(newDist<d[mY][mX]){
                d[mY][mX]=newDist;
                que.push({-newDist,mY,mX});
            }
        }
    }
}

int main(void){
    int tc=0;
    while(true){
        cin>>n;
        if(n==0){
            break;
        }

        // init graph
        graph.clear();
        for(int i=0;i<n;i++){
            vector<int> tmp;
            tmp.clear();
            for(int j=0;j<n;j++){
                int a;
                scanf("%d",&a);
                tmp.push_back(a);
            }
            graph.push_back(tmp);
        }

        // init distance
        d.clear();
        for(int i=0;i<n;i++){
            vector<int> tmp;
            tmp.clear();
            for(int j=0;j<n;j++){
                tmp.push_back(INF);
            }
            d.push_back(tmp);
        }

        // call dijkstra
        dijkstra();
        cout<<"Problem "<<++tc<<": "<<d[n-1][n-1]<<endl;
    }
}