[ 백준 ] 22116번 - 창영이와 퇴근 (C++)

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

22116번: 창영이와 퇴근

 

 

[ 문제풀이 ]

 

1. 격자를 입력받고, arr 배열에 저장합니다.

 

2. visited 배열을 만들어 해당 구간에 도착했을 때 경사로 차가 가장 적었을 때의 값을 저장합니다.

 

3. ans에 경사로 차 중 가장 큰 값을 저장합니다.

 

4. 다익스트라를 이용하여 경사로의 높이차가 작은 구간부터 방문하고, N - 1, N - 1 좌표에 도착하면 ans를 출력합니다.

 

[ 소스코드 ]

#include<iostream>
#include<queue>
#include<cmath>
 
using namespace std;
 
struct node {
    int y, x, h;
};
 
struct cmp {
    bool operator()(node right, node left) {
        return left.h < right.h;
    }
};
 
int N;
int arr[1000][1000];
int visited[1000][1000];
int ans;
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,-1,1 };
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> arr[i][j];
            visited[i][j] = 1111111111;
        }
    }
 
    priority_queue<node, vector<node>, cmp> pq;
    pq.push({ 0,0,0 });
    visited[0][0] = 0;
 
    while (!pq.empty()) {
        const int y = pq.top().y;
        const int x = pq.top().x;
        const int h = pq.top().h;
        pq.pop();
 
        if (visited[y][x] < h) continue;
 
        ans = max(ans, h);
 
        if (y == N - 1 && x == N - 1) {
            cout << ans;
            return 0;
        }
 
        for (int i = 0; i < 4; i++) {
            const int yy = y + dy[i];
            const int xx = x + dx[i];
 
            if (yy >= 0 && yy < N && xx >= 0 && xx < N) {
                int diff = abs(arr[y][x] - arr[yy][xx]);
                if (visited[yy][xx] > diff) {
                    visited[yy][xx] = diff;
                    pq.push({ yy,xx,diff });
                }
            }
        }
    }
}