문제

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

나의 코드

"""

"""

from collections import deque

N, M, oil = map(int, input().split()) # N:격자판크기, M:승객수, oil:연료의 양
pan = [ list(map(int, input().split())) for _ in range(N) ] # 0:빈칸, 1:벽
x, y = map(int, input().split()) # 운전자 위치 정보
x, y = x-1, y-1
route = [ list(map(int, input().split())) for _ in range(M) ] # 승객의 출발지와 도착지를 담은 정보
for i in range(M):
    for j in range(4):
        route[i][j] -= 1


dx, dy = [0, 0, -1, 1], [-1, 1, 0, 0]
def search(x, y): # 시작 좌표를 받으면 최단 경로 배열을 리턴하는 함수

    visited = [ [False] * N for _ in range(N) ]
    visited[x][y] = True
    dis = [ [-1] * N for _ in range(N) ] # 최단거리를 기록할 배열
    dis[x][y] = 0
    q = deque([(x, y)])

    while q:
        px, py = q.popleft()

        for k in range(4):
            mx = px + dx[k]
            my = py + dy[k]

            if (0 <= mx < N and 0 <= my < N):
                if pan[mx][my] == 0 and not visited[mx][my]:
                    visited[mx][my] = True
                    dis[mx][my] = dis[px][py] + 1
                    q.append((mx, my))

    return dis


def oil_check(): # 기름이 떨어지는지 체크하는 함수
    if oil < 0: # ★ '<=' 하면 안되는 이유는 -> "승객을 목적지로 이동시킨 동시에 연료가 바닥나는 경우는 실패한 것으로 간주하지 않는다." 이 문장때문이다.
        return True
    return False


for _ in range(M):

    dis = search(x, y) # 택시 위치를 넘겨주어 최단 거리 배열을 리턴받음

    move = []
    for i in range(len(route)): # 승객의 우선순위를 정하기 위한 반복문
        st_x, st_y, en_x, en_y = route[i]

        if dis[st_x][st_y] == -1: # 최단 거리가 갱신이 안되었다는건 택시가 해당 거리로 도달할 수 없음을 의미하므로 -1을 출력하고 stop
            print(-1)
            exit(0)
        else:
            move.append([dis[st_x][st_y], st_x, st_y, en_x, en_y])

    # 현재 위치에서 최단거리가 가장 짧은 승객을 고른다.
    # 그런 승객이 여러 명이면 그중 행 번호가 가장 작은 승객을, 그런 승객도 여러 명이면 그중 열 번호가 가장 작은 승객을 고른다.
    move.sort()

    consume_oil, st_x, st_y, en_x, en_y = move[0]

    oil -= consume_oil

    if oil_check():  # 기름이 다 떨어지면 True반환
        print(-1)
        exit(0)

    x, y = st_x, st_y # 택시 위치 이동

    dis = search(x, y)

    consume_oil = dis[en_x][en_y]

    oil -= consume_oil

    if oil_check(): # 기름이 다 떨어지면 True반환
        print(-1)
        exit(0)

    oil += (consume_oil * 2)

    x, y = en_x, en_y

    route.remove([st_x, st_y, en_x, en_y])

print(oil)
    

설명

1. search() 함수의 기능은 BFS를 이용하여 최단 거리 배열을 반환해주는 역할

참고 자료