[백준] 11909번 : 배열 탈출 (C++)

11909번 : 배열 탈출

---

문제)

상수는 2차원 배열 A[1..n][1..n] (n≥2, n은 자연수)을 가지고 있습니다. 이 배열의 각 원소는 1 이상 222 이하의 정수입니다.

배열을 가지고 놀던 상수를 본 승현이는, 질투심이 불타올라 상수를 A[1][1]에 가둬 버렸습니다! 최소한의 양심이 있던 승현이는 A[n][n]에 출구를 만들어 놓고 이 사실을 상수에게 알려줬습니다.

 

 

상수는 가능한 한 빨리 출구인 A[n][n]에 도달하고자 합니다. 상수가 A[i][j]에 있다고 가정했을 때, 상수는 최단 경로로 이동하기 위해 아래와 같은 조건을 만족하며 이동합니다.

1. 1≤i,j<n이라면, 상수는 A[i][j+1] 또는 A[i+1][j]로만 건너갑니다.
2. i=n,1≤j<n이라면, A[i][j+1]로만 건너갑니다.
3. 1≤i<n,j=n이라면 A[i+1][j]로만 건너갑니다.
4. i=j=n인 경우 바로 출구로 갑니다.

 

그러나 건너갈 때에도 제약이 따릅니다. 상수가 A[a][b]에서 A[c][d]로 건너가려면 A[a][b]>A[c][d]를 만족해야 합니다. 상수는 왜인지 이런 조건을 만족하면서 이동할 수 없을 것 같았습니다. 다행히도, 승현이가 상수를 배열에 가둬버리기 전에, 상수는 배열의 각 원소에 버튼을 만들어 놓아서, 이 버튼을 누르면 해당 원소의 값이 1 증가하도록 했습니다. (물론 상수는 자신이 위치해 있는 원소의 버튼만 누를 수 있습니다.) 이 버튼 덕분에, 상수는 항상 배열을 탈출할 수 있습니다!

 

 

[그림 3] n=2라고 가정합시다. A[1][1]=5>A[1][2]=2이므로, 상수는 A[1][1]에서 A[1][2]로 건너갈 수 있습니다. 상수가 A[1][1]에서 A[2][1]로 건너가려면, A[1][1]에 있는 버튼을 두 번 눌러 A[1][1]의 값을 7로 만들면 됩니다.

하지만 버튼을 한 번 누르는 데에는 1원의 비용이 듭니다. 상수는 돈을 가능한 한 적게 들이면서 배열을 탈출하고자 합니다. 상수를 도와주세요.

 

 

 

입력 :

첫 번째 줄에 n이 주어집니다. (n ≤ 2,222)

다음에 n개 줄이 주어집니다. 이 중 i(1≤i≤n)번째 줄에는 n개의 수 A[i][1],A[i][2],⋯,A[i][n−1],A[i][n]이 공백을 사이로 두고 차례대로 주어집니다.

 

 

 

출력 :

첫 번째 줄에 상수가 배열을 탈출하기 위해 들여야 할 최소 비용(원 단위)을 출력합니다.

 

 

 

 

 

풀이)

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
 
#define INF 9999999
 
using namespace std;
 
int n;
int vec[2223][2223];
int dist[2223][2223];
 
int dx[] = { 1, 0 };
int dy[] = { 0, 1 };
 
void dijkstra()
{    // 우선순위 큐의 내부 요소를 vector를 사용하게 되면
    // 시간 초과가 나게 되므로 pair<int, pair<int, int>> 를 사용해야 한다.
    priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>,
                     greater<pair<int, pair<int, int>>>> pq;
    pq.push({ 0, {0, 0} });
    dist[0][0] = 0;
 
    while (!pq.empty())
    {
        int d = pq.top().first;
        int x = pq.top().second.first;
        int y = pq.top().second.second;
        pq.pop();
 
        if (dist[x][y] < d) continue;
 
        for(int i = 0; i < 2; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if (0 > nx || nx >= n) continue;
            if (0 > ny || ny >= n) continue;
 
            // 기본적으로 시간은 d를 그대로 가며
            int nd = d;
            // 다음 배열이 더 클 경우 버튼을 누른 만큼 추가한다.
            if (vec[x][y] <= vec[nx][ny])
            {
                nd += (vec[nx][ny] - vec[x][y]) + 1;
            }
 
            if (nd < dist[nx][ny])
            {
                dist[nx][ny] = nd;
                pq.push({ nd, { nx, ny } });
            }
        }
    }
 
    cout << dist[n - 1][n - 1];
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> n;
    fill(&dist[0][0], &dist[2222][2223], INF);
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> vec[i][j];
        }
    }
 
    dijkstra();
 
    return 0;
}

---

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

11909번: 배열 탈출