BOJ #4485 - 녹색 옷 입은 애가 젤다지?

https://icpc.me/4485

# 문제 분류
최단 경로 찾기 (Dijkstra Algorithm)

풀이 접근 방법 :

 

1. 결국 바둑판처럼 생긴 격자에서 최단 경로를 찾는 것과 다를 바가 없다.

2. 시작점 (0, 0)과 끝점 (n-1, n-1)이 정해져 있으므로 Dijkstra 알고리즘을 사용하자.

---

페어 두개를 사용해서 좌표와 가중치를 표현해줬는데, 벡터로 해도 될지는 모르겠다.

벡터는 비교 연산자가 잘 정의되어 있어서,,, 벡터로 시도해보지는 않았다.

정 해야겠다면 bool operator< overloading으로 해결할 수는 있을듯 ?

 

별 다른 것은 없다. 주의할 점은 0과 n-1에서 범위 제한을 해줄 필요가 있다는 것이다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
 
using namespace std;
 
typedef pair<int, int> p;
typedef pair<int, p> pp;
 
int INF = 1e9;
int N, cnt = 1, res;
priority_queue<pp, vector<pp>, greater<pp>> pq;
 
int main(){
    while(1){
        scanf("%d", &N);
        if(!N) break;
 
        int arr[130][130] = {0};
        int d[130][130];
        bool visited[130][130] = {0};
 
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                int tmp;
                scanf("%d ", &tmp);
                arr[i][j] = tmp;
                d[i][j] = INF;
            }
        }
 
        pq.push(make_pair(arr[0][0], make_pair(0, 0)));
        d[0][0] = arr[0][0];
 
        while(!pq.empty()){
            int vx = pq.top().second.first;
            int vy = pq.top().second.second;
            pq.pop();
 
            if(visited[vx][vy]) continue;
            visited[vx][vy] = true;
 
            if(vx > 0){
                int w = arr[vx-1][vy];
 
                if(d[vx-1][vy] > d[vx][vy] + w){
                    d[vx-1][vy] = d[vx][vy] + w;
                    pq.push(make_pair(d[vx-1][vy], make_pair(vx-1, vy)));
                }
            }
            if(vy > 0){
                int w = arr[vx][vy-1];
 
                if(d[vx][vy-1] > d[vx][vy] + w){
                    d[vx][vy-1] = d[vx][vy] + w;
                    pq.push(make_pair(d[vx][vy-1], make_pair(vx, vy-1)));
                }
            }
            if(vx < N-1){
                int w = arr[vx+1][vy];
 
                if(d[vx+1][vy] > d[vx][vy] + w){
                    d[vx+1][vy] = d[vx][vy] + w;
                    pq.push(make_pair(d[vx+1][vy], make_pair(vx+1, vy)));
                }
            }
            if(vy < N-1){
                int w = arr[vx][vy+1];
 
                if(d[vx][vy+1] > d[vx][vy] + w){
                    d[vx][vy+1] = d[vx][vy] + w;
                    pq.push(make_pair(d[vx][vy+1], make_pair(vx, vy+1)));
                }
            }
        }
 
        res = d[N-1][N-1];
 
        printf("Problem %d: ", cnt++);
        printf("%d\n", res);
    }
 
    return 0;
}