[백준 / 19238] 스타트 택시 - Python

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

19238번: 스타트 택시

<풀이>

어렵다.

해당 문제는 '다익스트라 알고리즘(Dijkstra)'을 응용하여 풀었다.

2021.03.18 - [# Coding/# Algorithm] - [보기 쉬운 Algorithm] 다익스트라(Dijkstra) 알고리즘 - Python

[보기 쉬운 Algorithm] 다익스트라(Dijkstra) 알고리즘 - Python

<전체 코드>

import sys
import heapq


def dijkstra(graph, n, row, col):
    temp_visit = [[float('inf') for _ in range(n)] for _ in range(n)]

    temp_visit[row][col] = 0

    queue = [[0, [row, col]]]

    drow = [-1, 0, 1, 0]
    dcol = [0, 1, 0, -1]

    while queue:
        cur_distance, cur = heapq.heappop(queue)
        cur_row, cur_col = cur

        if temp_visit[cur_row][cur_col] < cur_distance:
            continue

        for i in range(4):
            new_row = cur_row+drow[i]
            new_col = cur_col+dcol[i]
            if new_col == n or new_row == n:
                continue
            elif new_row == -1 or new_col == -1:
                continue

            if graph[new_row][new_col] == 1:
                continue
            if cur_distance+1 < temp_visit[new_row][new_col]:
                temp_visit[new_row][new_col] = cur_distance+1
                heapq.heappush(queue, [cur_distance+1, [new_row, new_col]])

    return temp_visit


N, M, fuel = map(int, sys.stdin.readline().split())

graph = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

row, col = map(int, sys.stdin.readline().split())

client = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]
client.sort()
fail = False
while client:
    table = dijkstra(graph, N, row-1, col-1)

    min_dis = float('inf')
    min_per = -1

    for i in range(M):
        cur_row, cur_col, des_row, des_col = client[i]
        if table[cur_row-1][cur_col-1] < min_dis:
            min_dis = table[cur_row-1][cur_col-1]
            min_per = i
    if min_dis == float('inf'):
        fail = True
        break

    cur_row, cur_col, row, col = client.pop(min_per)
    M -= 1

    drive = dijkstra(graph,  N, cur_row-1,
                     cur_col-1)[row-1][col-1]
    if drive == float('inf'):
        fail = True
        break
    elif min_dis + drive > fuel:
        fail = True
        break

    else:
        fuel += drive - min_dis

if fail:
    print(-1)
else:
    print(fuel)