백준 2842 집배원 한상덕 (파이썬)

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

2842번: 집배원 한상덕

생각보다 많이 까다로웠던 문제

이동할 수 있는 최소 높이와 최대 높이의 범위를 바꿔가면서 bfs를 한 후에 최소값을 찾는 방법으로 해결

높이가 백만까지 가능하기 때문에 시간 초과가 발생하지 않을지 확신은 없었는데 시간 제한이 3초라서 풀 수 있었다

 

1. P나 K가 입력되면 home에 저장한다.

2. 높이를 입력받은 후 높이 중 최소, 최대를 구하고 home의 최소, 최대를 구한다.

3. 구해야할 범위의 왼쪽은 전체 높이 중 최소와 home 높이 중 최소 사이에 있고

   오른쪽은 home 높이 중 최대와 전체 높이 중 최대 사이에 있다. 이에 맞춰 왼쪽, 오른쪽 리스트를 만든다

4. home의 맨 처음 값을 bfs에 입력하여 모든 K와 P에 방문할 수 있는지 검증한다

5. 방문 할 수 없으면 오른쪽 범위를 넓혀주고 방문할 수 있으면 왼쪽 범위를 좁혀 최소 피로도를 찾아간다

6. 왼쪽과 오른쪽 값이 확정되었으면 그 다음 범위도 확인해야 하므로 왼쪽, 오른쪽을 둘 다 증가시킨다

7. 모든 경우를 확인한 후 저장한 최소값을 출력

from collections import deque
import sys

input = sys.stdin.readline
dx = [1, -1, 0, 0, 1, 1, -1, -1]
dy = [0, 0, 1, -1, 1, -1, 1, -1]

def bfs(x, y, left, right):
    q = deque()
    c = [[0]*n for _ in range(n)]
    q.append([x, y])
    c[x][y] = 1
    while q:
        x, y = q.popleft()
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n:
                if left <= h[nx][ny] <= right and not c[nx][ny]:
                    c[nx][ny] = 1
                    q.append([nx, ny])

    for i, j in home:
        if not c[i][j]:
            return 0
    return 1

n = int(input())

a, home = [], []
for i in range(n):
    row = list(input().strip())
    a.append(row)
    for j, k in enumerate(row):
        if k == 'P' or k == 'K':
            home.append([i, j])

h, temp_set = [], set()
for i in range(n):
    row = list(map(int, input().split()))
    h.append(row)
    for k in row:
        temp_set.add(k)
temp_list = list(sorted(temp_set))
l_min = min(temp_list)
r_max = max(temp_list)

l_max, r_min = sys.maxsize, 0
for i, j in home:
    l_max = min(l_max, h[i][j])
    r_min = max(r_min, h[i][j])

lq, rq = [], []
for k in temp_list:
    if l_min <= k <= l_max:
        lq.append(k)
    if r_min <= k <= r_max:
        rq.append(k)

ans = sys.maxsize
i, j = 0, 0
while i < len(lq) and j < len(rq):
    l_flag, r_flag = 0, 0
    if bfs(home[0][0], home[0][1], lq[i], rq[j]):
        ans = min(ans, rq[j] - lq[i])
        i += 1
        l_flag = 1
    else:
        if l_flag and r_flag:
            i += 1; j += 1
        else:
            j += 1
            r_flag = 1
print(ans)