[Python] 백준 / platinum / 2842 : 집배원 한상덕

문제 링크 : https://www.acmicpc.net/problem/2842

BFS + 투포인터 + 이분 탐색 문제. 다음과 같이 해결했다.

1. 마을 행렬과 고도 행렬을 입력받고, 마을의 모든 고도 값은 height_arr 에, 집과 우체국의 고도는 house_arr 에 담는다. 이때 중복한 고도 값은 고려해줄 필요가 없기 때문에 set 타입에 담는다.

2. set 타입이었던 두 자료를 list 타입으로 형변환하고 정렬한다.

3. 문제가 "가장 높은곳과 가장 낮은 곳의 고도 차이가 가장 작은 것을 구하시오" 이기 때문에 가장 높은곳과 가장 낮은 곳의 값을 투 포인터 알고리즘으로 탐색 시도한다.

4. for 문으로 낮은 곳의 고도 값을 탐색한다. for 문 안에서, 현재 탐색중인 가장 낮은 곳의 고도 (temp_min) 일 때의 가장 피로도를 낮게 하는 고도값을 이분 탐색으로 찾는다.
   • 이 때 temp_min 값이 "집이나 우체국 중 고도가 가장 낮은 곳" 보다 높아지면 더 이상 탐색을 할 필요가 없기 때문에 break 한다.
   • check 함수를 선언해서 값을 찾았는데, 여기서 BFS 를 사용했다.
   • answer_of_max 는 각 이분탐색으로 나온 결과 값이다.

처음엔 height_arr 을 선언하지 않고 그냥 고도를 1씩 증가시키면서 탐색을 했었다. 하지만 이 문제에서 고도는 1,000,000보다 작거나 같은 자연수이기 때문에 시간초과가 나게 됐었다. 위 흐름처럼 로직을 짰더니 정답처리를 받을 수 있었다.

파이썬 코드

from collections import deque
import sys
direction = [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, 1), (1, -1)]
N = int(sys.stdin.readline())
graph = []
height = []
height_arr = set()
house_arr = set()
num_of_house = 0
P = [0, 0]

for _ in range(N):
    graph.append(list(sys.stdin.readline()))

for _ in range(N):
    height.append(list(map(int, sys.stdin.readline().split())))

for i in range(N):
    for j in range(N):
        height_arr.add(height[i][j])

        if graph[i][j] == 'P':
            P = [i, j]
            house_arr.add(height[i][j])
        elif graph[i][j] == 'K':
            house_arr.add(height[i][j])
            num_of_house += 1

height_arr = sorted(list(height_arr))
house_arr = sorted(list(house_arr))


# 이 고도 차이로 마을 배달을 완료할 수 있는지.
def check(l, r):
    # 모든 집들을 다 방문하는지 수 체크
    k = 0
    visit = [[False] * N for _ in range(N)]
    q = deque()
    q.append((P[0], P[1]))
    visit[P[0]][P[1]] = True

    # 우체국이 범위안에 들어갈 수 없다면
    if (l > height[P[0]][P[1]]) or (r < height[P[0]][P[1]]):
        return False

    while q:
        x, y = q.popleft()
        if graph[x][y] == 'K':
            k += 1

        for d in direction:
            nx = x + d[0]
            ny = y + d[1]

            if 0 <= nx < N and 0 <= ny < N and not visit[nx][ny]:
                if l <= height[nx][ny] <= r:
                    q.append((nx, ny))
                    visit[nx][ny] = True

    return True if k == num_of_house else False


answer = 987654321
max_height = max(height_arr)
max_house = max(house_arr)
min_house = min(house_arr)


for i in range(len(height_arr)):
    temp_min = height_arr[i]
    if temp_min > min_house:
        break
    # 구간의 최댓값을 이분 탐색
    left = max_house
    right = max_height
    answer_of_max = 987654321

    while left <= right:
        mid = (left + right) // 2
        result = check(temp_min, mid)
        if result:
            answer_of_max = mid
            right = mid - 1
        else:
            left = mid + 1

    answer = min(answer, answer_of_max - temp_min)

print(answer)