[acmicpc] 19238. 스타트 택시(python)

최단거리 - bfs 알고리즘

---

정답코드

import sys
input=sys.stdin.readline
from collections import deque
dirx=[1,0,-1,0]
diry=[0,1,0,-1]

def bfs(y,x):
    visited=[[-1]*N for _ in range(N)]
    queue=deque()
    queue.append((y,x))
    visited[y][x]=0

    while queue:
        cur=queue.popleft()
        for i in range(4):
            ny=cur[0]+diry[i]
            nx=cur[1]+dirx[i]
            if 0<=ny<N and 0<=nx<N and board[ny][nx]==0 and visited[ny][nx]==-1:
                visited[ny][nx]=visited[cur[0]][cur[1]]+1
                queue.append((ny,nx))
    return visited

def check_dist(visited, guests):
    for i in range(len(guests)):
        py, px=guests[i][0]-1, guests[i][1]-1
        guests[i].append(visited[py][px])
    guests.sort(key=lambda x : (-x[-1],-x[0],-x[1]))

if __name__ == "__main__":
    N,M,G=map(int,input().split())
    board=[list(map(int,input().split())) for _ in range(N)]
    texi_y, texi_x=map(int,input().split())
    guests=[list(map(int,input().split())) for _ in range(M)]


    for i in range(M):
        # 1. 가장 가까운 손님한테 가기
        visited = bfs(texi_y - 1, texi_x - 1)
        check_dist(visited,guests)
        guest=guests.pop()
        py,px,dy,dx,dist=guest[0],guest[1],guest[2],guest[3],guest[-1]

        # 2. 손님 데려다주기
        visited=bfs(py-1,px-1)
        dist_d=visited[dy-1][dx-1]
        texi_y,texi_x=dy,dx

        if dist==-1 or dist_d==-1: # 손님을 데려다줄 수 없는 경우
            print(-1)
            exit(0)

        G-=(dist+dist_d)
        if G<0: # 연료가 모두 소진된 경우
            print(-1)
            exit(0)
        G+=dist_d*2

    print(G)

 

 

---

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

19238번: 스타트 택시