[백준] 19238 스타트 택시 [Python, 파이썬]

• 문제 : https://www.acmicpc.net/problem/19238
• BFS

 

from collections import deque
from heapq import heappop, heappush

n, m, e = map(int, input().split()) # 맵크기, 승객 수, 연료 양
Map = [list(map(int, input().split())) for _ in range(n)]
taxi = list(map(int, input().split()))  # 택시 좌표

pa_lst = [] # 사람, 도착 좌표 리스트

for i in range(m):
    px, py, ax, ay = map(int, input().split())  # 출발 행, 열, 목적지 행, 열
    Map[px-1][py-1] = -1       # 사람 위치 (-1)
    pa_lst.append([px, py, ax, ay])


def take(d, x, y):
    global e

    if Map[x][y] == -1: # 도착지에 손님이 있으면
        return (0, x, y)
    
    Q = deque([(d, x, y)])   # 택시 출발 위치
    visit = [[0] * n for _ in range(n)]
    visit[x][y] = 1
    heap = []
    mx, my = [0, 0, -1, 1], [-1, 1, 0, 0]

    limit = 99999999

    while Q:
        d, x, y = Q.popleft()

        if d > limit:   # 최소 거리보다 멀어지면
            continue

        for i in range(4):
            nx, ny = x + mx[i], y + my[i]
            if 0 <= nx < n and 0 <= ny < n: # 맵 크기 안 벗어나게
                if visit[nx][ny] == 0 and Map[nx][ny] != 1:
                    Q.append((d+1, nx, ny))
                    visit[nx][ny] = 1
                    if Map[nx][ny] == -1: # 가장 가까운 승객을 만났다.
                        heappush(heap, (d, nx, ny))
                        limit = d   # 최소 거리 제한
   
    e -= d  # 태우러 가면서 쓴 연료
    if e < 0:
        print(-1)
        exit()

    if not heap:    # 태울 수 없으면
        print(-1)
        exit()

    return heappop(heap)

def arrival(d, px, py, ax, ay):
    global e
    Q = deque([(d, px, py)])    # 승객 위치
    visit = [[0] * n for _ in range(n)]
    visit[px][py] = 1
    mx, my = [0, 0, -1, 1], [-1, 1, 0, 0]

    while Q:
        d, x, y = Q.popleft()

        if x == ax and y == ay: # 목적지 도착
            e -= d
            if e < 0:
                print(-1)
                exit()
            e += d * 2  # 다시 충전

            return (x, y)
        
        for i in range(4):
            nx, ny = x + mx[i], y + my[i]
            if 0 <= nx < n and 0 <= ny < n: # 맵 크기 안 벗어나게
                if visit[nx][ny] == 0 and Map[nx][ny] != 1:
                    Q.append((d+1, nx, ny))
                    visit[nx][ny] = 1
    print(-1)
    exit()

cnt = 0
d, x, y = 0, taxi[0]-1, taxi[1]-1   # 택시 시작점
ax, ay = 0, 0

while cnt < m:
        # take(깊이, x, y)
        d, px, py = take(d, x, y)   # p = (d, 사람x, 사람y) 를 반환 받음
        Map[px][py] = 0 # 태운 사람 자리 0으로 바꿈

        for i in range(len(pa_lst)):  # 도착지 찾기
            if px+1 == pa_lst[i][0] and py+1 == pa_lst[i][1]:
                ax, ay = pa_lst[i][2], pa_lst[i][3]
                pa_lst.pop(i)   # 리스트에서 제거
                break
        
        x, y = arrival(0, px, py, ax-1, ay-1)

        d = 0
        cnt += 1
    
print(e)