15573 채굴

# Python 3으로 제출할 시 시간초과 발생
# PyPy 3으로 제출 필요
import sys
from collections import deque

n, m, k = map(int, sys.stdin.readline().split())

stone = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]


def bfs(d):
    queue = deque()
    visited = [[False] * m for _ in range(n)]
    dx, dy = [-1, 0, 1, 0], [0, -1, 0, 1]
    cnt = 0

    # 가장자리 부분 채굴 시도
    for i in range(m):
        visited[0][i] = True
        if stone[0][i] <= d:
            queue.append((0, i))
            cnt += 1
    for i in range(1, n):
        visited[i][0] = True
        if stone[i][0] <= d:
            queue.append((i, 0))
            cnt += 1
        visited[i][m-1] = True
        if stone[i][m-1] <= d:
            queue.append((i, m-1))
            cnt += 1

    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 visited[nx][ny]:
                continue

            visited[nx][ny] = True
            if stone[nx][ny] <= d:
                queue.append((nx, ny))
                cnt += 1

    return cnt


start, end = 1, 10**6
min_d = end
while start <= end:
	# 채굴기 강도 : mid
    mid = (start + end) // 2
    my_k = bfs(mid)

    if my_k >= k:
        min_d = min(min_d, mid)
        end = mid - 1
    else:
        start = mid + 1

sys.stdout.write(str(min_d))

15573 채굴