백준 22116: 창영이와 퇴근 [C/C++]

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

22116번: 창영이와 퇴근

 

#include <iostream>
static const auto fastio = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
 
using namespace std;
int n;
int grid[1111][1111];
int visited[1111][1111];
int dy[4] = {0, 1, 0, -1};
int dx[4] = {1, 0, -1, 0};
int dp[1111][1111];
int dfs(int y, int x, int h) {
    if (y < 1 or x < 1 or x > n or y > n or visited[y][x]) return 0;
    if (y == n and x == n) return 1;
    if (dp[y][x] >= 0) return dp[y][x];
    visited[y][x] = 1;
    int t = 0;
    for (int i = 0; i < 4; i++) 
        if (abs(grid[y][x] - grid[y + dy[i]][x + dx[i]]) <= h)
            t = max(t, dfs(y + dy[i], x + dx[i], h));
    dp[y][x] = t;
    visited[y][x] = 0;
    return t;
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) cin >> grid[i][j];
    int l = 0, r = 1000000000, mid;
    while (l <= r) {
        mid = (l + r) / 2;
        for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) dp[i][j] = -1;
        if (dfs(1, 1, mid)) r = mid - 1;
        else l = mid + 1;
    }
    cout << l;
    return 0;
}
 

이분탐색 및 다이나믹 프로그래밍을 활용하는 문제입니다.