백준 27068번 이미지 보정 작업

문제 링크

파라메트릭 서치 문제. 두 구역의 선명도의 가장 큰 차이를 $mid$로 놓고 이분탐색을 하면 풀 수 있다.

각 구역은 모두 $X$ 이하의 선명도를 가지고 있다. 이 때 구역 $a, b (a\le b)$의 선명도 차이가 $mid$ 이상이라고 해 보자. 둘 중 선명도가 더 작은 구역인 $a$를 보정해서 $X$로 키워야 차이가 줄어들 것이다. 그런데 $X-b$가 $mid$보다 크다면 $b$도 보정해야 한다. 즉, 선명도가 $X - mid$보다 작은 값이라면 모두 보정해야 한다.

따라서 우리는 주어진 이미지를 살펴보면서, 인접 구역과 선명도 차이가 $mid$보다 큰 구역을 찾고, 거기서부터 bfs 돌리면서 보정을 해 나가야한다.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;

constexpr int dy[4] = {1, -1, 0, 0}, dx[4] = {0, 0, 1, -1};
ll N, M, K, X, arr[500][500];

int bfs(int y, int x, ll diff, bool changed[500][500]) {
    int ret = 1;

    queue<pair<int, int>> q;
    q.emplace(y, x);
    changed[y][x] = true;
    while (!q.empty()) {
        auto [y, x] = q.front();
        q.pop();

        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i], nx = x + dx[i];
            if (ny >= N || ny < 0 || nx >= M || nx < 0) continue;
            if (changed[ny][nx]) continue;
            if (arr[ny][nx] < X - diff) {
                changed[ny][nx] = true;
                q.emplace(ny, nx);
                ret++;
            }
        }

    }

    return ret;
}

int get_cnt(ll diff) {
    int ret = 0;
    bool changed[500][500] = {0};

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (arr[i][j] >= X - diff) continue;
            if (changed[i][j]) continue;
            for (int k = 0; k < 4; k++) {
                int ny = i + dy[k], nx = j + dx[k];
                if (ny >= N || ny < 0 || nx >= M || nx < 0) continue;
                if (abs(arr[i][j] - arr[ny][nx]) > diff) {
                    ret += bfs(i, j, diff, changed);
                    break;
                }
            }
        }
    }

    return ret;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M >> K >> X;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> arr[i][j];
        }
    }

    ll lo = 0, hi = X;
    while (lo <= hi) {
        ll mid = (lo + hi) / 2;
        int cnt = get_cnt(mid);
        // cout << mid << ' ' << cnt << '\n';
        if (cnt > K) lo = mid + 1;
        else hi = mid - 1;
    }

    cout << lo << '\n';

    return 0;
}

$10^9, 10^{18}$ 같은 숫자가 범위로 주어지면 이분 탐색, 매개 변수 탐색을 의심해보도록 하자.