[Gold III] 채굴 - 15573

문제 링크

성능 요약

메모리: 233364 KB, 시간: 3644 ms

분류

그래프 이론, 그래프 탐색, 이분 탐색, 너비 우선 탐색, 매개 변수 탐색, 격자 그래프

문제 설명

채굴기를 이용하여 이 광물들을 채굴하려고 한다. 채굴기는 공기와 맞닿아 있는 광물 하나를 골라 채굴할 수 있다. 바닥과 광물과만 맞닿아 있으면 채굴할 수 없다. 채굴기의 성능 D에 대해, 채굴기는 강도가 D이하인 광물들만 채굴할 수 있다. 원하는 광물의 수 K 이상을 채굴할 수 있는 최소의 D를 구하여라.

입력

첫째 줄에 N, M,K가 주어진다. (1 ≤N, M> ≤ 1000, 1 ≤ K ≤ N × M) 둘째 줄부터 맨 위의 광물들부터 순서대로 N줄 동안 M개의 광물의 강도 Si, j가 주어진다.(i = 1, 2, ..., N, j = 1, 2, ..., M) (1 ≤ Si, j ≤ 106)

출력

K개 이상의 광물을 채굴할 수 있는 최소의 D를 구하여라.

---

문제 풀이

문제 분석

이 문제는 N x M 크기의 광산에서 K개 이상의 광물을 채굴할 수 있는 최소 강도 D를 찾는 문제입니다. 채굴은 공기와 맞닿아 있는 광물부터 시작하며, 채굴기의 성능 D보다 강도가 낮은 광물만 채굴할 수 있습니다. 즉, 주어진 격자 형태의 광산에서 외부와 연결된 부분부터 시작하여 특정 강도 이하의 광물들을 탐색하고, 그 수가 K개 이상이 되는 최소 강도를 찾아야 합니다.

접근 방법

이 문제는 이분 탐색과 BFS(너비 우선 탐색)을 결합하여 해결할 수 있습니다.

1. 이분 탐색: 가능한 최소 강도(left)와 최대 강도(right)를 설정하고, 이분 탐색을 통해 적절한 강도 D를 찾습니다.
2. BFS: 특정 강도 D가 주어졌을 때, BFS를 사용하여 채굴 가능한 광물의 수를 계산합니다. 광산의 가장자리에 있는 광물부터 시작하여, 강도가 D 이하인 인접한 광물들을 탐색합니다.
3. 결정 함수: BFS를 통해 얻은 채굴 가능한 광물의 수가 K 이상이면, 더 작은 강도로도 가능한지 확인하기 위해 right를 mid로 갱신합니다. 그렇지 않으면, 더 큰 강도가 필요하므로 left를 mid로 갱신합니다.

구현 설명

1단계: 입력 및 초기 설정

• n, m, k 값을 입력받습니다.
• graph 리스트에 광산의 강도 정보를 입력받습니다.
• directions 리스트에 상, 하, 좌, 우 방향을 나타내는 튜플을 저장합니다.

2단계: BFS 함수 구현 (BFS(num))

• visited 2차원 리스트를 생성하여 방문 여부를 추적합니다.
• queue (deque)를 사용하여 BFS를 수행합니다.
• cnt 변수를 초기화하여 채굴 가능한 광물의 수를 저장합니다.
• 광산의 가장자리에 있는 광물들을 확인합니다. 만약 강도가 num (현재 이분 탐색 값) 이하이고 방문하지 않았다면, queue에 추가하고 cnt를 증가시키며 방문 표시합니다.
• queue가 빌 때까지 다음을 반복합니다.
  • queue에서 좌표 (x, y)를 꺼냅니다.
  • directions에 따라 인접한 광물 (sx, sy)을 확인합니다.
  • 만약 (sx, sy)가 광산 내부에 있고, 방문하지 않았으며, 강도가 num 이하라면, queue에 추가하고 cnt를 증가시키며 방문 표시합니다.
• cnt가 k 이상이면 True를 반환하고, 그렇지 않으면 False를 반환합니다.

3단계: 이분 탐색 수행

• left를 0으로, right를 10⁶ + 1 (최대 강도 + 1)로 초기화합니다.
• left + 1 < right 조건을 만족하는 동안 다음을 반복합니다.
  • mid를 (left + right) // 2로 계산합니다.
  • BFS(mid)를 호출하여 mid 강도로 k개 이상의 광물을 채굴할 수 있는지 확인합니다.
  • 만약 BFS(mid)가 True를 반환하면, 더 작은 강도로도 가능한지 확인하기 위해 right = mid로 갱신합니다.
  • 그렇지 않으면, 더 큰 강도가 필요하므로 left = mid로 갱신합니다.

4단계: 결과 출력

• 이분 탐색이 종료되면, right에 최소 강도 D가 저장됩니다. right를 출력합니다.

⏱복잡도 분석

• 시간 복잡도: 이분 탐색의 시간 복잡도는 O(log(10⁶))입니다. BFS의 시간 복잡도는 O(N*M)입니다. 따라서 전체 시간 복잡도는 O(log(10⁶) * N*M)입니다. 문제 조건에서 N, M <= 1000 이므로, 최악의 경우 O(1000 * 1000 * log(10^6)) 입니다. log(10^6)은 상수이므로, 대략 O(10⁶)의 시간복잡도를 가집니다.
• 공간 복잡도: graph, visited, queue 등의 자료구조를 사용하므로 공간 복잡도는 O(N*M)입니다.

핵심 포인트

1. 이분 탐색 적용: 문제에서 '최소' 값을 구해야 하므로 이분 탐색을 활용하여 효율적으로 탐색 범위를 좁혀나갈 수 있습니다.
2. BFS를 활용한 연결 요소 탐색: 특정 강도 이하의 광물들이 연결되어 있는지를 확인하고, 채굴 가능한 광물의 수를 효율적으로 계산하기 위해 BFS를 사용합니다.
3. 가장자리부터 탐색 시작: 광산의 가장자리에 있는 광물부터 채굴을 시작해야 한다는 조건에 따라, BFS를 시작점을 적절하게 설정해야 합니다.

풀이 코드

import sys
from collections import deque

input = sys.stdin.readline

n,m,k = map(int, input().split())

graph = []

for i in range(n):
    graph.append(list(map(int, input().split())))

directions = [(1,0),(-1,0),(0,1),(0,-1)]
def BFS(num):
    visited = [[False] *m for i in range(n)]
    queue = deque()
    cnt = 0
    for i in range(n):
        if graph[i][0] <= num:
            queue.append((i,0))
            cnt+=1
            visited[i][0] = True

        if graph[i][m-1] <= num:
            queue.append((i,m-1))
            cnt+=1
            visited[i][m-1] = True
    
    for i in range(1,m-1):
        if graph[0][i] <= num:
            cnt+=1
            queue.append((0,i))
            visited[0][i] = True

    while queue:
        x,y = queue.popleft()
        for dx,dy in directions:
            sx,sy = x+dx, y+dy
            if 0<=sx<n and 0<=sy<m and not visited[sx][sy] and graph[sx][sy] <= num:
                cnt+=1
                queue.append((sx,sy))
                visited[sx][sy] = True

    if cnt >= k:
        return True

    return False
left = 0
right = 10**6 + 1
while left + 1 < right:
    mid = (left + right) // 2 
    if BFS(mid):
        right = mid
    else:
        left = mid

print(right)