[ 백준 4485 ] 녹색 옷 입은 애가 젤다지? (c/c++)

https://www.acmicpc.net/problem/4485

 

 

[ 문제 요약 ]

[0][0]에서 시작하여 상하좌우로 한칸씩 이동하여 [N-1][N-1]에 도착하는데 걸리는 최소 금액을 출력한다.

 

 

[ 문제 풀이 ]

1. 다익스트라를 이용해서 상하좌우를 이동하며 계산한다.

 

 

[ 소스 코드 ]

#include <bits/stdc++.h>
using namespace std;

int T = 0, N, ans;
int arr[130][130], D[130][130];

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

void Find() {
    for (int i=0; i<N; i++) for (int j=0; j<N; j++) D[i][j] = 1e9;
    priority_queue<pair<int, pair<int, int>>> pq;
    pq.push(make_pair(-arr[0][0], make_pair(0, 0)));
    D[0][0] = arr[0][0];

    while (!pq.empty()){
        int cost = -pq.top().first;
        int x = pq.top().second.first;
        int y = pq.top().second.second;
        pq.pop();

        for (int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx >= 0 && ny >= 0 && nx < N && ny < N){
                int ncost = cost + arr[nx][ny];
                if (D[nx][ny] > ncost){
                    D[nx][ny] = ncost;
                    pq.push(make_pair(-D[nx][ny], make_pair(nx, ny)));
                }
            }
        }
    }
    ans = D[N-1][N-1];
}

int main() {
    while (++T){
        cin >> N;
        if (N == 0) break;
        for (int i=0; i<N; i++) for (int j=0; j<N; j++) cin >> arr[i][j];
        Find();
        cout << "Problem " << T << ": " << ans << "\n";
    }
    return 0;
}

 

 

[ 주의할 점 ]

BFS를 이용하여 모든 모든 경우를 계산해서 최단 거리로 가도 가능하다.