[BOJ - 4485] 녹색 옷 입은 애가 젤다지? (C++)

  문제

  접근방법

잃는 금액을 최소화 -> 최단 경로 문제

상하좌우로 이동 (dx[], dy[]로 선언), 가중치 존재

-> 다익스트라 알고리즘을 사용한 문제 해결

 

dist[][] 배열 -> 각 칸까지의 현재까지 최소 비용을 저장, 초기값은 (0,0)에서 시작, 이외에는 INT_MAX값으로 초기화.

 

  코드

#include <iostream>
#include <queue>

using namespace std;

const int INF = 2147483647;
const int Max_size = 126;

int N;
int thief_rupee[Max_size][Max_size];
int dist[Max_size][Max_size];

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

bool inArea(int x, int y) {
    return x >= 0 && y >= 0 && x < N && y < N;
}

int dijkstra() {
    priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<>> pq;

    // 초기 상태를 설정
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            dist[i][j] = INF; // 모든 경로 비용을 무한대로
        }
    }

    // 시작점 설정 (0,0)에서 출발
    dist[0][0] = thief_rupee[0][0];
    pq.push({dist[0][0], {0, 0}});

    while (!pq.empty()) {
        auto [cur_cost, pos] = pq.top();
        int x = pos.first; int y = pos.second;
        pq.pop();

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

            if (inArea(nx, ny)) {
                int new_cost = cur_cost + thief_rupee[nx][ny];

                if (new_cost < dist[nx][ny]) { // 더 적은 루피를 잃는 경로 -> 갱신
                    dist[nx][ny] = new_cost;
                    pq.push({new_cost,{nx, ny}});
                }
            }
        }
    }

    return dist[N-1][N-1];
}


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

    int count = 1;
    while (true) {
        cin >> N;

        if (N == 0) return 0;

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

        int result = dijkstra();

        cout << "Problem " << count << ": " << result << '\n';

        count++;
    }
}

처음 풀어보는거라 주석 달면서 문제 푸니까 이해가 빠름(도움이 많이 되네용)

 

  링크

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