[python] 백준 19238 스타트 택시

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

19238번: 스타트 택시

 

문제 해결

• 정해진 출발지에서 가장 가까이 있는 사람(같은 거리에 있으면 행이 작은 위치,열이 작인 위치 순으로 있는 사람)을 픽업한 다음 그 사람의 목적지에 도달시키면서 이동하면서 남은 연료를 출력하는 문제이다.(부족하면 -1)
• 따라서 출발지에서부터 각 위치의 최단 거리를 구한다음 가장 작은 사람을 픽업하러 간 후 그 위치에서 (정해진)목적지까지 거리를 계산하면 되는 간단한 문제이다.
• 모든 사람은 각 다른 위치에 있지만 각 사람의 목적지는 같을 수도 있고 한 사람의 위치에 다른 사람이 목적지일 수도 있다는  것을 주의해야한다.

 

CODE

from collections import deque
def bfs(x,y):
    global l
    que = deque()
    visited = [[-1]*n for _ in range(n)]
    visited[x][y] = 0
    dxs = [-1,0,0,1]; dys = [0,-1,1,0]
    que.append((x,y,0))
    while que:
        nowx, nowy, cnt = que.popleft()
        for i in range(4):
            nx = nowx+dxs[i]; ny = nowy+dys[i]
            if 0<=nx<n and 0<=ny<n and visited[nx][ny]==-1 and A[nx][ny] != 1:
                visited[nx][ny] = visited[nowx][nowy] + 1
                que.append((nx,ny,visited[nx][ny]))
    candidate = []    
    for p in P:
        sx,sy,ex,ey = p
        candidate.append((sx,sy,ex,ey,visited[sx][sy]))
    candidate.sort(key=lambda x: (x[4],x[0], x[1]))
    nx, ny,ex,ey, visited[nx][ny] = candidate[0]
    P.remove((nx,ny,ex,ey))
    if visited[nx][ny] == -1:
        return -1
    # print(nx,ny,visited[nx][ny])
    l -= visited[nx][ny]
    # print(f'픽업 하는데 소모된 주유량 {visited[nx][ny]}')
    if l <0:
        return -1
    A[nx][ny] = 0
    for i in range(n):
        for j in range(n):
            visited[i][j] = -1
    visited[nx][ny] = 0
    que1 = deque()
    que1.append((nx,ny))
    while que1:
        x, y = que1.popleft()
        for dx, dy in zip(dxs,dys):
            nx = x +dx; ny = y + dy
            if 0<=nx<n and 0<=ny<n and visited[nx][ny]==-1 and A[nx][ny] != 1:
                visited[nx][ny] = visited[x][y] + 1
                que1.append((nx,ny))
    if visited[ex][ey] == -1:
        return -1
    l -= visited[ex][ey]
    if l<0:
        return -1
    else:
        l += visited[ex][ey]*2
        return n*ex+ey
if __name__=='__main__':
    n, m, l = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(n)]
    P = []
    res = [ [] for _ in range(401)]
    startx, starty = map(int, input().split())
    startx -= 1; starty -= 1
    for i in range(2,m+2):
        x, y, ex, ey = map(int, input().split())
        A[x-1][y-1] = i
        res[n*(ex-1)+ey-1].append(i)
        P.append((x-1,y-1,ex-1,ey-1))
    t = 0
    while len(P):
        num= bfs(startx,starty)
        if num==-1:
            print(-1)
            break
        startx = num//n; starty = num%n
        # print(startx,starty)
    else:
        print(l)