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

문제

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

---

문제 요약

N × N 배열 각 칸마다 도둑루피의 크기가 주어지고, 해당 칸을 지나면 그만큼 소지금을 잃게 된다.

 

(0, 0)부터 (N - 1, N - 1)까지 이동해야 할 때, 잃는 금액의 최소 값을 출력한다.

 

상하좌우 인접한 곳으로 1칸씩 이동할 수 있다.

---

코드

#include <iostream>
#include <queue>
#include <tuple>

# define ll long long

using namespace std;

int board[150][150];

bool visited[150][150];

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

// dist[i][j]: (0, 0)부터 (i, j)까지 최단 거리
int dist[150][150];

priority_queue<tuple<int, int, int>> pq;

int main() {
    // 입출력 단축 코드
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    // 테스트 케이스 번호
    int t = 1;

    while (true) {
        int n; 
        cin >> n;

        if (n == 0) break;

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

        // 최단 거리 초기화
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dist[i][j] = 1e9;
            }
        }

        // 초기 값 우선순위 큐에 삽입
        dist[0][0] = board[0][0];
        pq.push({ -dist[0][0], 0, 0 });

        // 다익스트라 진행
        while (!pq.empty()) {
            int w, x, y;
            tie(w, x, y) = pq.top();
            pq.pop();
            w = -w;

            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;
                // if (dist[nx][ny] != 1e9) continue;

                if (dist[nx][ny] > w + board[nx][ny]) {
                    dist[nx][ny] = w + board[nx][ny];
                    pq.push({ -dist[nx][ny], nx, ny });
                }
            }

        }
        
        cout << "Problem " << t << ": " << dist[n - 1][n - 1] << "\n";

        t++;
    }
    

    return 0;
}

---

코드 설명

한 시작점에서 한 도착점까지 최소 비용을 구하는 문제이다.

 

특정 시작점에서 다른 모든 정점으로 가는 거리를 각각 구해주는 알고리즘인 다익스트라를 이용한다.

 

1. N × N 배열의 각 칸의 도둑 루피 크기를 입력 받는다.

 

2. 최단 거리를 모두 1,000,000,000으로 초기화한다. (무한대로 가정)

 

3. 시작점을 우선 순위 큐에 넣고 하나씩 빼며 다익스트라를 진행한다.

+ dist[i][j]: (0, 0)부터 (i, j)까지 최단 거리

 

4. dx, dy 기법을 통해 인접한 칸에 접근하면서 우선 순위 큐에 삽입한다.

(인덱스 범위를 벗어나지 않도록 주의한다.)

 

5. 도착점까지의 최소 비용을 출력한다.

---

고찰

다익스트라 진행 시, if문을 통해 갱신이 되는 경우만 우선순위 큐에 원소를 삽입하는 것을 잊지 말자.

if (dist[nx][ny] > w + board[nx][ny]) {
    dist[nx][ny] = w + board[nx][ny];
    pq.push({ -dist[nx][ny], nx, ny });
}

 

예전에 min()을 사용했다가 갱신이 되지 않는 경우에도 삽입되어 시간 초과로 실패한 적이 있다.