고오급 알고리즘 스터디 - 2

import sys
from collections import deque

n, m, k, X = map(int, sys.stdin.readline().split())
origin_graph = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
dx, dy = [-1, 0, 1, 0], [0, -1, 0, 1]

start, end = 0, X
res = X
while start <= end:
    mid = (start + end) // 2
    graph = [[origin_graph[i][j] for j in range(m)] for i in range(n)]
    cnt = 0

    queue = deque()
    check = False
    for x in range(n):
        for y in range(m):
            if graph[x][y] == X:
                continue

            for i in range(4):
                nx, ny = x + dx[i], y + dy[i]
                if nx < 0 or nx >= n or ny < 0 or ny >= m:
                    continue

                if graph[nx][ny] > graph[x][y] and abs(graph[nx][ny] - graph[x][y]) > mid:
                    graph[x][y] = X
                    cnt += 1
                    queue.append((x, y))
                    break

    while queue:
        x, y = queue.popleft()
            
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue

            if abs(X - graph[nx][ny]) > mid:
                graph[nx][ny] = X
                cnt += 1
                queue.append((nx, ny))

    if cnt <= k:
        res = min(res, mid)
        end = mid - 1
    else:
        start = mid + 1

print(res)

풀이

이진 탐색(매개변수 탐색) 을 통해 찾고 싶은 값 : 인접한 두 구역의 선명도의 가장 큰 차이의 최솟값

• 초기 시작지점 : 0, 종료지점 : X
• 인접한 두 구역의 선명도의 가장 큰 차이 : mid
  

어디를 보정해야 하는가?

• 인접한 두 수의 선명도 차이가 mid 보다 큰 경우 보정 필요
• 인접한 수 중에서 큰 수를 보정한다면 여전히 선명도 차이는 mid보다 큰 값을 유지하므로 작은 수를 보정한다.
  -> "이미지의 한 구역을 보정하면 해당 구역의 선명도를 최대 선명도인 $X$로 만들 수 있다." 라는 조건 때문

27068 이미지 보정 작업