스타트 택시 파이썬 백준 19238

문제

input

첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다.

다음 줄부터 N개의 줄에 걸쳐 백준이 활동할 영역의 지도가 주어진다. 0은 빈칸, 1은 벽을 나타낸다.

다음 줄에는 백준이 운전을 시작하는 칸의 행 번호와 열 번호가 주어진다. 행과 열 번호는 1 이상 N 이하의 자연수이고, 운전을 시작하는 칸은 빈칸이다.

그다음 줄부터 M개의 줄에 걸쳐 각 승객의 출발지의 행과 열 번호, 그리고 목적지의 행과 열 번호가 주어진다. 모든 출발지와 목적지는 빈칸이고, 모든 출발지는 서로 다르며, 각 손님의 출발지와 목적지는 다르다.

output

모든 손님을 이동시키고 연료를 충전했을 때 남은 연료의 양을 출력한다. 단, 이동 도중에 연료가 바닥나서 다음 출발지나 목적지로 이동할 수 없으면 -1을 출력한다. 모든 손님을 이동시킬 수 없는 경우에도 -1을 출력한다.

TODO

while 남은 손님 : 
	1.가장 가까운 손님 찾기 
		-> 무슨 상어였나 그거랑 같은데 거리가 같다면 높이 우선, 높이도 같다면 왼쪽 우선 
		bfs우선순위를 상 좌 우 하 로 두면 안됨->반례 많음 
		처음 택시 위치와 손님 위치는 같을 수 있음.
	2.손님의 목적지로 모시기 
		모신 후 손님 태우고나서 목적지까지 쓴 연료*2를 충전 
        손님 삭제
	
	3.태울수 있는 손님이 없거나, 기름이 다 떨어지면 알아볼 수 있게 return 

CODE

import sys 
n,m,oil= map(int,sys.stdin.readline().split()) 
world = [list(map(int,sys.stdin.readline().split())) for _ in range(n)]
start = list(map(int,sys.stdin.readline().split())) 
infor = [list(map(int,sys.stdin.readline().split())) for _ in range(m)]
start.append(oil)
start[0] -= 1
start[1] -= 1 
move_key = {}
for i,(inf) in enumerate(infor): 
    x1,y1,x2,y2 = inf 
    world[x1-1][y1-1] = 2+i 
    move_key[2+i] = [x2-1,y2-1]
from collections import deque 

dx = [0,0,-1,1]
dy = [1,-1,0,0]
def search1(world,start): 
    if world[start[0]][start[1]] != 0 : 
        return start
    q = deque([start]) 
    check = [[True for _ in range(n)] for _ in range(n)]
    succ = []
    succ_oil = -2
    rex,rey = float('inf'),float('inf')
    while q : 
        x,y,o = q.popleft()
        if o == -1 : 
            return -1,-1,-1
        if (not succ) or succ_oil +1 == o : 
            for px,py in zip(dx,dy): 
                nx,ny = x+px, y+py
                if 0<=nx<n and 0<=ny<n and o>0 and check[nx][ny] and world[nx][ny] != 1 : 
                    q.append([nx,ny,o-1])
                    check[nx][ny] = False 
                    if world[nx][ny] != 0 and world[nx][ny] != 1 : 
                        succ.append([nx,ny,o-1])
                        succ_oil = o-1 
        elif succ and o == succ_oil : 
            for suc in succ : 
                if rex > suc[0] : 
                    rex,rey = suc[0],suc[1]
                elif rex == suc[0] and rey>suc[1] : 
                    rey = suc[1]
            break
    return [rex,rey,succ_oil]

def search_dist(world, start, move_key): 
    q = deque([start]) 
    check = [[1 for _ in range(n)] for _ in range(n)]
    sx,sy,so = start
    check[move_key[world[sx][sy]][0]][move_key[world[sx][sy]][1]] = 2
    
    del move_key[world[sx][sy]]
    world[sx][sy] = 0
    while q : 
        x,y,o = q.popleft() 
        if o == -1 :
            return [-1,-1,-1] 
        for px,py in zip (dx,dy): 
            nx,ny = x+px, y+py 
            if 0<=nx<n and 0<=ny<n and o>0 and check[nx][ny] != 0  and world[nx][ny] != 1 : 
                if check[nx][ny] == 2 : 
                    # no = o-1 + 2*(so - (o-1))
                    no = 2*so - o + 1
                    return [nx,ny,no]
                check[nx][ny] = 0
                q.append([nx,ny,o-1])
    return [-1,-1,-1]


def taxi (world, start, move_key):
    while move_key:
        start = search1 (world,start)
        if start[0] == -1 or start[2] == -2 : 
            return -1 
        
        start = search_dist(world,start,move_key)
        if start[0] == -1 or start[2] == -2:
            return -1
    return start[2] 

print(taxi(world,start,move_key))

회고

한큐에 통과하려고 연습햇는데 실패했다.. 택시와 손님의 위치가 겹칠수도 있는데 생각하지 못했다.