백준 4486번 녹색 옷을 입은 애가 젤다지?

백준 4486번 녹색 옷을 입은 애가 젤다지?

#include <iostream>
#include<vector>
#include<queue>
#include<string>
#include<cstring>
#include<algorithm>
#include<cstring>
using namespace std;
int arr[126][126];
int n;
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };
bool visited[126][126];
 
int route() {
    priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
    pq.push({ arr[0][0],{0,0} });
    visited[0][0] = 1;
    while (!pq.empty()) {
        int y = pq.top().second.first;
        int x = pq.top().second.second;
        int cost = pq.top().first;
        pq.pop();
        if (y == n - 1 && x == n - 1) return cost;
 
        for (int i = 0; i < 4; i++) {
            int nexty = y + dy[i];
            int nextx = x + dx[i];
            if (0 <= nexty && nexty < n && 0 <= nextx && nextx < n) {
                if (!visited[nexty][nextx]) {
                    pq.push({ cost + arr[nexty][nextx],{nexty,nextx} });
                    visited[nexty][nextx] = 1;
                }
            }
        }
    }
 
}
 
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int cnt = 1;
    do {
        memset(visited, 0, sizeof(visited));
        cin >> n;
        if (!n) return 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                cin >> arr[i][j];
    
    
    
        cout << "Problem " << cnt++ << ": " << route() << endl;
 
 
    } while (n);
    
    return 0;
 
}
 

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

ㅋㅋ 문제내용을 너무 재밌게 쓰셧네요. 난이도 자체는 매우 쉬운편이였습니다.

우선 순위큐를 활용해서 쉽게 풀 수 있는 문제였네요. 주석을 따로 달지 않아도 될 것 같습니다.