[백준][구현][heap] 스타트 택시

스타트 택시

 

• 내 풀이
  • distance(i, j): 현재 위치 (i, j)에서 그래프 전체까지의 최단 거리를 BFS로 계산하는 함수
  • 매 반복마다 현재 택시 위치에서 distance()를 호출해 전체 위치까지의 거리를 구한 뒤,
  • 모든 손님의 출발 위치를 기준으로 거리 정보를 heap에 저장
    • 선택된 손님에 대해 다시 한 번 distance()를 호출해, (출발지 → 도착지)까지의 최단 거리를 구함
    • 총 필요 연료 = 택시 → 손님 출발지 거리 + 출발지 → 도착지 거리
      • 연료가 부족하면 -1을 출력하고 종료
      • 충분하다면 연료를 차감한 뒤 도착지까지 거리 * 2만큼 보충

from collections import deque
import heapq

n, m, oil = map(int, input().split())
graph = [[0 for _ in range(n+1)]]+[[0] +list(map(int, input().split())) for _ in range(n)]

taxi_i, taxi_j = map(int, input().split())
customers = [list(map(int, input().split())) for _ in range(m)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


def distance(i, j):
    queue = deque([(i, j)])
    visited[i][j] = 0
    while queue:
        x, y = queue.popleft()

        for k in range(4):
            nx = x+dx[k]
            ny = y+dy[k]

            if nx <= 0 or ny <= 0 or nx > n or ny > n:
                continue
            if graph[nx][ny] == 1:
                continue
            if visited[nx][ny] <= visited[x][y]+1:
                continue
            visited[nx][ny] = visited[x][y]+1
            queue.append((nx, ny))


ti, tj = taxi_i, taxi_j
while customers:
    visited = [[float('inf')]*(n+1) for _ in range(n+1)]
    distance(ti, tj)
    hq = []
    for idx, customer in enumerate(customers):
        si, sj, ei, ej = customer
        heapq.heappush(hq, (visited[si][sj], si, sj, ei, ej, idx))

    cur_d, cur_si, cur_sj, cur_ei, cur_ej, cur_idx = heapq.heappop(hq)

    visited = [[float('inf')]*(n+1) for _ in range(n+1)]
    distance(cur_si, cur_sj)
    nxt_d = visited[cur_ei][cur_ej]

    if oil < cur_d+nxt_d:
        oil = -1
        break
    else:
        oil -= (cur_d+nxt_d)
        oil += 2*nxt_d

    customers.pop(cur_idx)
    ti, tj = cur_ei, cur_ej

print(oil)