[Python] 15573번 채굴

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

15573번: 채굴

---

 

23/12/31

 

 

2023년 마지막 날에 해결한 문제로, BFS와 이분 탐색을 섞은 파라메트릭 문제이다.

 

파라메트릭 서치 연습으로 아주 적절한 문제인 듯 하다.

 

---

 

문제 접근 방식:

 

 

문제에서 요구하는 것은 최솟값을 요구하고 있고, 이 값은 특정 값 이상을 넘어가는 최솟값이므로 파라메트릭 서치를 통해 구현할 수 있다.

 

채굴기의 성능 $D$와 광산의 모습을 입력으로 받아서 BFS를 통해 실제로 채굴을 하고, 채굴된 광물의 개수와 필요한 광물의 개수 $K$을 비교하여 충분히 $K$개 이상으로 캘 수 있다면 True를, 아니라면 False를 리턴해주는 함수 mining을 구현했다.

 

채굴을 할 때에는 채굴기의 성능보다 높은 강도를 지닌 광물은 채굴할 수 없다고 했으므로, 이를 그대로 BFS에 녹여서 구현하면 된다.

 

채굴을 할 때마다 캔 광물의 개수를 하나 씩 올려주고, 나중에 필요한 광물의 개수와 서로 비교하면 된다.

 

파라메트릭 서치에서 필요한 판단 함수인데, 우리가 원하는 것은 $K$개 이상으로 캘 수 있는 채굴기의 성능 중에서 가장 낮은 성능 값을 찾고자 하는 것이므로, 이분 탐색을 활용하여 파라메트릭 서치 함수를 구현할 수 있다.

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 15573번 채굴
# 파라메트릭
import sys
input = sys.stdin.readline
from collections import deque

def mining(mine, N, M, K, D):
    total = 0
    dr, dc = [-1, 1, 0, 0], [0, 0, -1, 1]
    visited = [[0 for _ in range(M)] for _ in range(N)]
    queue = deque()
    for i in range(M):
        if mine[0][i] <= D:
            queue.append((0, i))
            visited[0][i] = 1
            total += 1
    for i in range(1, N):
        if mine[i][0] <= D:
            queue.append((i, 0))
            visited[i][0] = 1
            total += 1
        if mine[i][M-1] <= D:
            queue.append((i, M-1))
            visited[i][M-1] = 1
            total += 1
    while queue:
        row, col = queue.popleft()
        for i in range(4):
            now_r, now_c = row+dr[i], col+dc[i]
            if 0 <= now_r < N and 0 <= now_c < M:
                if mine[now_r][now_c] <= D and visited[now_r][now_c] == 0:
                    visited[now_r][now_c] = 1
                    total += 1
                    queue.append((now_r, now_c))
    if K <= total:
        return True
    else:
        return False

def parametric(judge, mine, N, M, K):
    start, end = 0, max(max(mine[i]) for i in range(N))
    while start < end:
        D = (start + end)//2
        if judge(mine, N, M, K, D) == False:
            start = D + 1
        else:
            end = D
    return end

def main():
    N, M, K = map(int, input().rstrip().split())
    mine = [list(map(int, input().rstrip().split())) for _ in range(N)]
    print(parametric(mining, mine, N, M, K))

main()