백준 4485번 녹색 옷 입은 애가 젤다지? (C++)

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

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

문제 요약

 

1. 테스트 케이스가 여러개 주어집니다.

2. 각 테이스케이스마다 n이 주어집니다. n이 0일 경우 테스트는 종료됩니다. (0<=n<=125)

3. n*n의 배열이 생성되며, 각 배열에 도둑루피의 크기가 주어집니다. (0<=도둑루피<=9)

4. 도둑루피의 크기만큼 해당 위치를 지나가기 위해서 루피(화폐)가 필요합니다. 

5. 최소한의 루피를 사용하여 시작위치 0,0에서 n-1,n-1로 가기위한 금액을 구하세요.

 

핵심 포인트

 

다익스트라를 활용해서 쉽게 풀 수 있는 문제입니다.

도둑루피의 크기를 최단거리로 생각하면 됩니다.

 

문제 풀이

 

1. 필요한 변수들을 선언하고 값을 입력받으세요.

 

int c = 1, t, y, x, ny, nx, my[]={0,1,0,-1}, mx[]={1,0,-1,0}; // 전역변수

// int main() 내부

while(true){
        int n = 0;
        cin >> n;
        if(n==0) break;
        vector<vector<int>> v(n,vector<int>(n,0));
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++) cin >> v[i][j];
        }
        cout << "Problem" << " " << c << ":" << " " << dijkstra(n,v) << "\n";
        c++;
    }

이때 정답으로 출력해야할 형식은 아래와 같은 형식을 띄고 있으니, 대문자와 소문자 및 숫자 출력에 주의하세요.

Problem 1: 20

 

2. 다음은 다익스트라의 함수 내부입니다.

int dijkstra(int &n, vector<vector<int>> &v){
    vector<vector<int>> zelda(n,vector<int>(n,MAX)); // 1
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; // 2
    zelda[0][0] = v[0][0]; // 3
    pq.push({0,0});
    while(!pq.empty()){ // 4
        y = pq.top().first; // 5
        x = pq.top().second;
        pq.pop();
        for(int i=0; i<4; i++){ // 6
            ny = y+my[i];
            nx = x+mx[i];
            if(ny<0||ny>n-1||nx<0||nx>n-1) continue; // 7
            if(zelda[ny][nx]>zelda[y][x]+v[ny][nx]){ // 8
                zelda[ny][nx] = zelda[y][x]+v[ny][nx]; 
                pq.push({ny,nx});
            }
        }
    }
    return zelda[n-1][n-1]; // 9
}

(1) n*n 사이즈의 zelda 벡터를 하나 생성합니다. 각 위치에 도달하기 위한 최소비용을 저장할 벡터입니다.

이때 벡터를 MAX로 초기화 해주는 것을 잊으면 안됩니다. MAX는 매크로 상수로 987654321로 초기화했습니다.

(2) pair<int,int>형 우선순위 큐를 구현합니다. 링크의 현재 위치를 저장할 우선순위 큐 입니다.

(3) zelda[0][0] = v[0][0]으로 초기화합니다. 동시에 우선순위 큐에 현재 위치 {0,0}을 저장합니다.

(4) pq가 빌때까지 while문을 돌립니다.

(5) 큐에 최상단에 위치한 현재 위치를 y,x에 저장하고 pq를 pop합니다.

(6) 4방위로 for문을 돌립니다.

(7) 만약 새로운 위치가 배열의 크기를 벗어난다면 continue를 합니다.

(8) 만약 새로운 위치에 저장된 누적 최소비용보다 > 위치의 누적 최소비용 + 새로운 위치로 가기 위한 비용일 경우, 

해당 위치에 새로운 누적 최소비용을 갱신해주고 pq에 새로운 위치를 삽입해줍니다.

(9) zelda[n-1][n-1]을 반환합니다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define MAX 987654321
using namespace std;

int c = 1, t, y, x, ny, nx, my[]={0,1,0,-1}, mx[]={1,0,-1,0};

int dijkstra(int &n, vector<vector<int>> &v){
    vector<vector<int>> zelda(n,vector<int>(n,MAX));
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    zelda[0][0] = v[0][0];
    pq.push({0,0});
    while(!pq.empty()){
        y = pq.top().first;
        x = pq.top().second;
        pq.pop();
        for(int i=0; i<4; i++){
            ny = y+my[i];
            nx = x+mx[i];
            if(ny<0||ny>n-1||nx<0||nx>n-1) continue;
            if(zelda[ny][nx]>zelda[y][x]+v[ny][nx]){
                zelda[ny][nx] = zelda[y][x]+v[ny][nx];
                pq.push({ny,nx});
            }
        }
    }
    return zelda[n-1][n-1];
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    while(true){
        int n = 0;
        cin >> n;
        if(n==0) break;
        vector<vector<int>> v(n,vector<int>(n,0));
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++) cin >> v[i][j];
        }
        cout << "Problem" << " " << c << ":" << " " << dijkstra(n,v) << "\n";
        c++;
    }
    return 0;
}