BOJ)5846 Tractor

문제: icpc.me/5846

n^2의 격자에서 한 점에서 4방향으로 일정 조건(둘의 차이가 k이하이면 이동 가능)을 만족하면 이동가능할 때

임의의 한점을 잡아 반 이상의 격자를 순회할 수 있는 최소의 k를 찾는 문제이다.

최대중의 최소를 구하는 문제이므로 파라메트릭 서치를 생각해볼 수 있다.

이 때 k를 mid값으로 정해놓은 뒤에 만족 여부를 확인하게 되는데

만족여부는 dfs를 통하여 확인할 수 있다. 

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int n, a[555][555], b[555][555];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int chk(int x, int y) {
    return 0 <= x&&x < n && 0 <= y&&y < n;
}
int dfs(int x, int y,int z) {
    b[x][y] = 1;
    for (int i = 0; i < 4; i++) {
        int cx = x + dx[i];
        int cy = y + dy[i];
        if (chk(cx, cy) && !b[cx][cy] && abs(a[x][y] - a[cx][cy]) <= z)
            b[x][y] += dfs(cx, cy, z);
    }
    return b[x][y];
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            scanf("%d", &a[i][j]);
    }
    int lo = 0;
    int hi = 1e6 + 1;
    while (lo < hi) {
        memset(b, 0, sizeof(b));
        int mid = (lo + hi) >> 1;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (!b[i][j])
                    ans = max(ans, dfs(i, j, mid));
            }
        }
        if (ans >= (n*n) / 2)
            hi = mid;
        else
            lo = mid + 1;
    }
    printf("%d\n", lo);
    return 0;
}