백준 4485번 [녹색 옷 입은 애가 젤다지?](C++) -yes6686- 티스토리

백준 문제 풀이: 4485 [녹색 옷 입은 애가 젤다지?]

---

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

문제 설명:

N×N 크기의 동굴에서 시작점 (0, 0)에서 도착점 (N-1, N-1)까지 이동하는 최소 비용을 계산하는 문제입니다. 각 칸에는 도둑 루피의 비용이 주어지며, 최소 루피 비용으로 도착점까지 도달해야 합니다.

---

문제 해결 코드

#include <iostream>
#include <queue>
#include <vector>
#define INF 1e9
using namespace std;

priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<>> pq;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int arr[126][126];
int dis[126][126];

void dijkstra(int n) {
    pq.push({arr[0][0], {0, 0}});
    dis[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) continue;

            int newCost = dis[x][y] + arr[nx][ny];
            if (dis[nx][ny] > newCost) {
                dis[nx][ny] = newCost;
                pq.push({newCost, {nx, ny}});
            }
        }
    }
}

int main() {
    int T = 1;
    while (true) {
        int n;
        cin >> n;
        if (n == 0) break;

        // 배열 초기화
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dis[i][j] = INF;
            }
        }

        // 입력
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cin >> arr[i][j];
            }
        }

        // 다익스트라 알고리즘 실행
        dijkstra(n);

        // 결과 출력
        cout << "Problem " << T << ": " << dis[n - 1][n - 1] << '\n';
        T++;
    }

    return 0;
}

---

코드 설명

• 핵심 알고리즘: 다익스트라 알고리즘을 사용하여 최소 비용 경로를 계산합니다. 시작점에서 도착점까지의 최단 거리를 계산하며, 각 칸의 루피 비용을 더해 나갑니다.
• 구현 세부사항:
  • dis[x][y]: (x, y)까지 도달하는 최소 비용
  • 다익스트라 알고리즘을 활용해 각 칸으로의 최소 비용을 업데이트
  • 입력이 여러 개의 테스트 케이스로 주어지므로 매번 배열을 초기화
• 시간 복잡도 분석: O(N² log N)
  • N은 동굴의 한 변의 길이
  • 우선순위 큐를 사용하는 다익스트라 알고리즘의 시간 복잡도

---

결과

각 테스트 케이스마다 시작점에서 도착점까지의 최소 비용을 정확히 계산합니다. 다익스트라 알고리즘을 사용하여 효율적으로 풀이했습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!