[BOJ/백준] 2842 집배원 한상덕 파이썬

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

2842번: 집배원 한상덕

 

바로 전에 풀이한 배열에서 이동과 아주 유사하다.

https://westmino.tistory.com/69

[BOJ/백준] 1981 배열에서 이동 파이썬

 

차이라면 BFS에서의 차이밖에 없다.

이 문제는 BFS시 반드시 들려야하는 점들이 있다. 해당 점들을 다 들렸을 때 피로도의 최소값을 구하는 문제이다.

 

일단 집의 개수를 세주고, 투포인터를 위해 높이 배열을 만들어 저장한다.

집은 이동한 거리 상관없이 지나만가면 되므로 그냥 BFS를 이용해 모든 점을 방문하면 된다.

모든 점을 방문해서 체크해줘도 되지만 반드시 들려야하는 집의 개수를 이용해도 된다.

나는 이를 이용했다.

배열에서 이동과 이점이 다를 뿐 문제는 거의 똑같다.

 

from sys import stdin
from collections import deque

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

n = int(input())

board = []
sx=sy=-1
home_cnt = 0
for x in range(n):
    board.append(input().strip())
    for y in range(n):
        if board[x][y] == 'P':
            sx,sy=x,y
        elif board[x][y] == 'K':
            home_cnt += 1

stamina_board = []
stamina_list = set()
for x in range(n):
    stamina_board.append(list(map(int, input().split())))
    for num in stamina_board[x]:
        stamina_list.add(num)
stamina_list = sorted(list(stamina_list))

visited = [[0]*n for _ in range(n)]
visited_num = 0
def solv():
    low=high=0
    answer = 9876543210
    while low < len(stamina_list) and high < len(stamina_list):
        if bfs(stamina_list[low],stamina_list[high]):
            if low == high:
                print(0)
                return
            else:
                answer = min(answer,abs(stamina_list[low]-stamina_list[high]))
                low += 1
        else:
            high += 1
    print(answer)
def bfs(low,high):
    global visited,visited_num
    if stamina_board[sx][sy] < low or stamina_board[sx][sy] > high:
        return False

    visited_num += 1
    q = deque([(sx,sy)])
    visited[sx][sy] = visited_num

    cnt = 0
    while q:
        x,y = q.pop()

        if board[x][y] == 'K':
            cnt += 1

        if cnt == home_cnt:
            return True
        for d in range(8):
            nx = x + dx[d]
            ny = y + dy[d]

            if point_validator(nx,ny):
                if low <= stamina_board[nx][ny] <= high:
                    visited[nx][ny] = visited_num
                    q.appendleft((nx,ny))

    return False
def point_validator(x,y):
    if x < 0 or y < 0 or x >= n or y >= n:
        return False
    elif visited[x][y] == visited_num:
        return False
    return True

solv()