[백준/C++] 4485번 : 녹색 옷 입은 애가 젤다지?

 

 

 

풀이

• 각 칸마다 해당 칸까지의 최소 소지금을 저장하기 위한 dist 배열을 선언한다. (최대값으로 초기화)
• 우선순위 큐를 사용하여 최소 칸부터 처리한다.
• 다익스트라 알고리즘에서 현재 칸에서 다음 칸으로 이동할 때 최소 소지금을 갱신하는 로직을 구현한다.
• (0, 0) 칸에서 시작. 초기 소지금은 해당 칸의 도둑루피 크기
• pq에 (초기 소지금, 시작 칸)을 넣는다.
• 우선순위 큐에서 하나씩 꺼내면서 해당 칸까지의 최소 소지금을 업데이트한다.
• 다음 칸으로 이동할 때의 소지금을 갱신하며 다음 칸으로 이동한다.

 

코드

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

using namespace std;

const int INF = INT_MAX;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int problemNum = 1;
    int N;

    while (cin >> N) {
        if (N == 0) break;

        vector<vector<int>> cave(N, vector<int>(N));
        vector<vector<int>> dist(N, vector<int>(N, INF));

        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                cin >> cave[i][j];
            }
        }

        dist[0][0] = cave[0][0];
        priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<>> pq;
        pq.push({dist[0][0], {0, 0}});

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

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

            if (dist[x][y] < cost) continue;

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

                if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;

                int newCost = cost + cave[nx][ny];
                if (dist[nx][ny] > newCost) {
                    dist[nx][ny] = newCost;
                    pq.push({newCost, {nx, ny}});
                }
            }
        }

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

    return 0;
}

 

 

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

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