[백준 19238] 스타트 택시(Python)

처음에 구현 했을 때, 택시와 가장 가까운 손님을 구하기 위해, 모든 손님에 대하여 BFS를 실행했다. 그 결과 시간 초과가 났었던 문제.

1. 요약

• 택시와의 거리가 가장 가까운 손님을 찾고, 손님이 있는 곳까지 간다.

• 가까운 거리가 2개 이상이면, 행이 더 작은 값을 갖는 손님을 선택한다. 만약 행도 같다면 열이 작은 값을 갖는 손님을 선택한다.

• 손님을 목적지까지 데려다 준다.

• 이동하는 동안 연료가 1씩 줄어들며, 만약 이동 중에 연료가 없으면 영업 종료를 한다.

• 목적지에 도착하면 사용한 연료x2와 남은 연료를 더해 연료를 충전한다.

• 서로 다른 손님은 서로 다른 위치, 목적지를 갖는다.

• 모든 손님을 태웠을 경우, 남아있는 연료를 구하고, 전부 못 태웠으면 -1를 출력한다.
  
  

2. 아이디어

• 택시가 있는 곳이 시작점이다.

• 한 번 이동 할 때마다, 연료를 1씩 소모하므로, 이동 거리 == 사용한 연료이다. 다시 말해, 사용한 연료를 구하기 위해, 별도의 변수를 사용할 필요가 없다. 오직 거리에 대한 변수 하나면 충분하다.

• 사용한 연료를 이동 할 때마다, 즉시 남아있는 연료에 반영하는 대신, 손님이 있는 곳 또는 손님의 목적지에 도착할 때, 나온 이동 거리를 이용하여 남아있는 연료에 반영한다.(만약 벽에 가로막혀 도착할 수 없다면, 거리는 무한이되고 남아있는 연료는 음의 값이 된다.)

• 택시와 가장 가까운 손님을 구하기 위해, BFS에서 얻은 이동 거리 테이블을 반환하고, 우선순위큐에 택시와 손님 사이에서 나온 결과를 [이동 거리, 행, 열, 위치에 관한 인덱스] 형식으로 삽입한다. 단, 유효한 결과여야한다.(e.g. 남아있는 연료, 이동 가능 여부)

• 목적지에 도착 할 때, 연료를 충전한다. 이 때, 남아있는 연료와 2x사용한 연료를 더하는 대신, 남아있는 연료와 목적지까지 이동한 거리를 더했다.(손님~목적지까지 이동거리 == 손님~목적지까지 사용한 연료)
  
  

3. 코드

import sys
from collections import deque
from heapq import heappop, heappush

n, m, f = map(int, sys.stdin.readline().rstrip().split())
arr = [[] for i in range(n)]
INF = int(1e9)
d = [[1,0], [-1,0], [0,1], [0,-1]]

for i in range(n):
    x = list(map(int, sys.stdin.readline().rstrip().split()))
    arr[i] = x


taxi_pos = list(map(int, sys.stdin.readline().rstrip().split()))
srcs = [[] for i in range(m)]
dsts = [[] for i in range(m)]

for i in range(m):
    src_y, src_x, dst_y, dst_x = map(int, sys.stdin.readline().rstrip().split())
    srcs[i] = [src_y, src_x]
    dsts[i] = [dst_y, dst_x]

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

def isin(y,x):
    if -1<y<n:
        if -1<x<n: return True
    return False

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

        for i in range(4):
            ny = y + d[i][0]
            nx = x + d[i][1]

            if isin(ny, nx):
                if not check[ny][nx]:
                    check[ny][nx] = True
                    if arr[ny][nx] != 1:
                        table[ny][nx] = table[y][x] + 1
                        q.append([ny, nx])
    
    return table

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

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

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

    return guest_index

# 손님의 목적지까지 가는 함수
def go_dst(guest_index):
    global f
    table = bfs()
    y, x = dsts[guest_index][0] - 1, dsts[guest_index][1] - 1
    dist = table[y][x]
    if f - 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 = srcs[guest_index]
    dist = go_dst(guest_index)
    if dist == -1:
        ok = False
        break
    f += dist
    taxi_pos = dsts[guest_index]
    cnt -= 1

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