문제
상수는 2차원 배열 A[1..n][1..n] (n≥2, n은 자연수)을 가지고 있습니다.
이 배열의 각 원소는 1 이상 222 이하의 정수입니다.
배열을 가지고 놀던 상수를 본 승현이는, 질투심이 불타올라 상수를 A[1][1]에 가둬 버렸습니다!
최소한의 양심이 있던 승현이는 A[n][n]에 출구를 만들어 놓고 이 사실을 상수에게 알려줬습니다.
상수는 가능한 한 빨리 출구인 A[n][n]에 도달하고자 합니다.
상수가 A[i][j]에 있다고 가정했을 때,
상수는 최단 경로로 이동하기 위해 아래와 같은 조건을 만족하며 이동합니다.
- 1≤i,j<n이라면, 상수는 A[i][j+1] 또는 A[i+1][j]로만 건너갑니다.
- i=n,1≤j<n이라면, A[i][j+1]로만 건너갑니다.
- 1≤i<n,j=n이라면 A[i+1][j]로만 건너갑니다.
- i=j=n인 경우 바로 출구로 갑니다.
그러나 건너갈 때에도 제약이 따릅니다.
상수가 A[a][b]에서 A[c][d]로 건너가려면 A[a][b]>A[c][d]를 만족해야 합니다.
상수는 왜인지 이런 조건을 만족하면서 이동할 수 없을 것 같았습니다.
다행히도, 승현이가 상수를 배열에 가둬버리기 전에,
상수는 배열의 각 원소에 버튼을 만들어 놓아서,
이 버튼을 누르면 해당 원소의 값이 1 증가하도록 했습니다.
(물론 상수는 자신이 위치해 있는 원소의 버튼만 누를 수 있습니다.)
이 버튼 덕분에, 상수는 항상 배열을 탈출할 수 있습니다!
하지만 버튼을 한 번 누르는 데에는 1원의 비용이 듭니다.
상수는 돈을 가능한 한 적게 들이면서 배열을 탈출하고자 합니다. 상수를 도와주세요.
입력
첫 번째 줄에 n이 주어집니다. (n ≤ 2,222)
다음에 n개 줄이 주어집니다. 이 중 i(1≤i≤n)번째 줄에는 n개의 수 A[i][1],A[i][2],⋯,A[i][n−1],A[i][n]이 공백을 사이로 두고 차례대로 주어집니다.
출력
첫 번째 줄에 상수가 배열을 탈출하기 위해 들여야 할 최소 비용(원 단위)을 출력합니다.
풀이
Priority_queue 를 활용해 다익스트라를 쉽게 구현할 수 있었다.
- Priority_queue 의 원소로 {현재 비용, {현재 x 좌표, 현재 y 좌표}} 를 넣고 오름차순으로 정렬해준다.
- 최소 개수를 기록할 2차원 배열 dp 를 생성해 가장 적은 비용을 기록한다.
- 우선순위 큐가 오름차순 정렬되어 있으므로, 끝방에 도착하자마자 다익스트라 순회를 마쳐도 된다.
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string>
#include <cstring>
#include <cmath>
#include <climits>
#include <unordered_map>
#include <bitset>
#include <tuple>
using namespace std;
#define N 2224
int n;
int v[N][N];
vector<vector<int>> dp;
int mx[] = { 1,0 };
int my[] = { 0,1 };
void solve()
{
priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
pq.push({ 0,{1,1} });
dp[1][1] = 0;
while (pq.size())
{
int cnt = pq.top().first;
int cx = pq.top().second.first;
int cy = pq.top().second.second;
int cur = v[cx][cy];
pq.pop();
if (cnt > dp[cx][cy])
continue;
if (cx == n && cy == n)
break;
for (int i = 0; i < 2; ++i)
{
int nx = cx + mx[i];
int ny = cy + my[i];
int node = v[nx][ny];
if (nx < 1 || ny < 1 || nx > n || ny > n) // 배열 밖 범위 검사
continue;
if (node < cur) // 버튼 클릭 없이 이동
{
if (dp[nx][ny] > cnt)
{
dp[nx][ny] = cnt;
pq.push({ cnt,{nx,ny} });
}
}
else if (node >= cur) // 버튼 클릭 필요
{
int d = node - cur + 1;
if (dp[nx][ny] > cnt + d) // 최소값인지 확인
{
dp[nx][ny] = cnt + d;
pq.push({ dp[nx][ny],{nx,ny} });
}
}
}
}
/* DP 배열 검사
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= n; ++j)
{
cout << dp[i][j] << ' ';
}
cout << '\n';
}*/
cout << dp[n][n];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n;
dp.resize(n + 1, vector<int>(n + 1, INT_MAX));
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= n; ++j)
{
cin >> v[i][j];
}
}
solve();
return 0;
}