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

02 Mar 2021 in Algorithm

문제 링크 : https://www.acmicpc.net/problem/4485

나의 풀이

도둑루피의 크기가 작을 수록 링크가 잃어버리는 금액이 최소가 되기 때문에 결국 (0,0)에서 (N-1, N-1) 까지의 최단 경로를 찾는 문제와 동일하기 때문에 다익스트라로 접근하였다.
유의할 점은 기존 다익스트라와 다르게 (0,0)에서 (0,0)까지의 최소 거리가 0이 아니라 입력받은 값이다.

풀이 코드 : 4485 녹색 옷 입은 애가 젤다지?

#include <iostream>
#include <vector>
#include <queue>

#define INF 2000000000

using namespace std;

int X[] = {1, -1, 0, 0};
int Y[] = {0, 0, 1, -1};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N, t = 0;
    while(true){
        t++;
        cin>>N;
        if(N==0) break;
        vector<vector<int>> map;
        vector<vector<int>> dist;
        vector<vector<int>> visit;

        map.resize(N);
        dist.resize(N);
        visit.resize(N);
        for(int i=0;i<N;i++){
            map[i].resize(N);
            dist[i].resize(N);
            visit[i].resize(N);
            for(int j=0;j<N;j++){
                cin>>map[i][j];
                visit[i][j] = 0;
                dist[i][j] = INF;
            }
        }

        priority_queue<pair<int, pair<int, int>>> pq;
        dist[0][0] = map[0][0];
        pq.push(make_pair(-dist[0][0], make_pair(0, 0)));
        while(!pq.empty()){
            int x = pq.top().second.first;
            int y = pq.top().second.second;

            pq.pop();
            
            if(visit[y][x] == 1) continue;
            visit[y][x] = 1;
            for(int i=0;i<4;i++){
                int next_x = X[i] + x;
                int next_y = Y[i] + y;
                if(next_x >= 0 && next_y >= 0 && next_x < N && next_y < N && visit[next_y][next_x] == 0){
                    if(dist[next_y][next_x] > dist[y][x] + map[next_y][next_x] )
                    {
                        dist[next_y][next_x] = dist[y][x] + map[next_y][next_x];
                        pq.push(make_pair(-dist[next_y][next_x], make_pair(next_x, next_y)));
                    }
                }
            }
        }

        cout<<"Problem "<<t<<": "<<dist[N-1][N-1]<<"\n";
    }
}

채점결과