백준 스타트 택시

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

19238번: 스타트 택시

정답코드

import sys
from collections import deque
import heapq
 
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
input = sys.stdin.readline

N,M,Fuel = map(int, input().split())
# 1: wall 2: 승객 3: taxi
board = []

for i in range(N):
    board.append(list(map(int, input().split())))
#taxi start
sx, sy = map(int, input().split()) 
taxi = (sx-1, sy-1)
# 손님 정보
customer = {}
for i in range(M):
    x, y, fx, fy = map(int, input().split())
    
    customer[(x-1, y-1)] = (fx-1, fy-1)
    board[x-1][y-1] = 2

def bfs(taxi):
    heap =[]
    x, y = taxi
    q = deque()
    q.append((x, y))
    visited = [[-1 for i in range(N)] for i in range(N)]
    visited[x][y] = 0
    while q:
        x, y = q.popleft()
        if board[x][y] == 2:
            heapq.heappush(heap, (visited[x][y], x, y))
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < N:
                if board[nx][ny] != 1 and visited[nx][ny] == -1:
                    visited[nx][ny] = visited[x][y] + 1
                    q.append((nx, ny))
    return heap

#start와 target 사이의 거리 반환
def calbfs(start, target): 
    x, y = start
    q = deque()
    q.append((x, y))
    visited = [[-1 for i in range(N)] for i in range(N)]
    visited[x][y] = 0
    while q:
        x, y = q.popleft()
        if target == (x, y):
            return visited[x][y]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < N:
                if board[nx][ny] != 1 and visited[nx][ny] == -1:
                    visited[nx][ny] = visited[x][y] + 1
                    q.append((nx, ny))
    #visited[target[0]][target[1]] == -1 이면 방문하지 못한것임
    return visited[target[0]][target[1]]     
           
cnt = 0
while 1:
    vheap = bfs(taxi)
    if len(vheap) == 0:
        break
    #distance = 택시와 손님사이의 거리
    distance, x, y = heapq.heappop(vheap)
    Fuel -= distance
    if Fuel < 0:
        Fuel = -1
        break

    destination = customer[(x, y)]
    #손님과 목적지 사이의 거리
    distance2 = calbfs((x, y), destination)
    if distance2 == -1:
        Fuel = -1
        break
    else:
        if Fuel < distance2:
            Fuel = -1
            break
        else:
            Fuel = Fuel + distance2    

    board[x][y] = 0
    taxi = destination
    cnt += 1
#모든 손님이 목적지에 도달했는지 확인
if cnt < M:
    print(-1)
else:
    print(Fuel)

손님과 목적지 사이의 거리 bfs로 구해야했어야 했는데 단순히 |x-fx| + |y-fy| 로 계산해서 처음에 계속 오답 처리가 되었었다.

왜그랬을까...

벽이 있다는 점을 고려하지 않았다,,,,