276. 스타트 택시

백준

1. Python

import sys
from collections import deque
from heapq import heappop, heappush
input = sys.stdin.readline
INF = int(1e9)

n, m, fuel = map(int,  input().split())
data = [list(map(int,input().split())) for i in range(n)]

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

taxi_pos = list(map(int, input().split()))
start = []
end = []

for _ in range(m):
    a, b, c, d = map(int, input().split())
    start.append([a, b])
    end.append([c, d])

picked = [False for _ in range(m)]

# 출발지와 도착지 거리 계산
def bfs():
    global taxi_pos, fuel
    sx, sy = taxi_pos[0] - 1, taxi_pos[1] - 1
    check = [[False] * n for _ in range(n)]
    table = [[INF] * n for _ in range(n)]
    q = deque()
    q.append((sx, sy))
    table[sx][sy] = 0
    check[sx][sy] = True
    
    while q:
        x, y= q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < n:
                if not check[nx][ny]:
                    check[nx][ny] = True
                    if data[nx][ny] != 1:
                        table[nx][ny] = table[x][y] + 1
                        q.append((nx, ny))
    
    return table

# 택시와 가까운 손님을 찾는 함수
def find_guest():
    global data, fuel, picked 
    table = bfs()
    pq = []

    for i in range(m):
        if not picked[i]:
            x, y = start[i][0] - 1, start[i][1] - 1
            dist = table[x][y]
            if fuel - dist >= 0:
                heappush(pq, [dist, x, y, i]) 

    if not pq: return -1
    dist, _, _, guest_index = heappop(pq)
    fuel -= dist
    picked[guest_index] = True

    return guest_index

# 손님의 목적지까지 가는 함수
def go_dst(guest_index):
    global fuel
    table = bfs()
    x, y = end[guest_index][0] - 1, end[guest_index][1] - 1
    dist = table[x][y]
    if fuel - dist < 0: 
        return -1
    return dist

# 실행코드
ok = True
cnt = m
while cnt:
    guest_index = find_guest()
    if guest_index == -1:
        ok = False
        break
    taxi_pos = start[guest_index]
    dist = go_dst(guest_index)
    if dist == -1:
        ok = False
        break
    fuel += dist
    taxi_pos = end[guest_index]
    cnt -= 1

if ok: 
    print(fuel)
else: 
    print(-1)