[BOJ] 19238 - 스타트 택시 (Python)

 

 

아이디어

 

연료가 남은 동안 손님들을 이동시키며 모든 손님을 이동시켰을 때 남은 연료를 출력한다.

 

 

풀이

 

import sys

input = sys.stdin.readline

delta = [(-1, 0), (0, 1), (1, 0), (0, -1)]

def solution():
    N, M, K = map(int, input().split())
    board = [list(map(lambda x: -int(x), input().split())) for _ in range(N)]
    des = dict()
    r, c = map(int, input().split())
    queue = [(r-1, c-1)]
    for i in range(1, M+1):
        s_r, s_c, e_r, e_c = map(lambda x: int(x)-1, input().split())
        board[s_r][s_c] = i
        des[(e_r, e_c)] = des.get((e_r, e_c), [])+[i]
    for _ in range(M):
        visited = [[0]*N for _ in range(N)]
        r, c = queue[0]
        visited[r][c] = 1
        if board[r][c]:
            num = board[r][c]
            board[r][c] = 0
        else:
            P = []
            while queue:
                r, c = queue.pop(0)
                for dr, dc in delta:
                    nr, nc = r+dr, c+dc
                    if N > nr >= 0 and N > nc >= 0:
                        if visited[nr][nc] == 0 and board[nr][nc] != -1:
                            visited[nr][nc] = visited[r][c]+1
                            if visited[r][c] <= K:
                                queue.append((nr, nc))
                                if board[nr][nc]:
                                    P.append((visited[r][c], nr, nc))
            if P:
                P.sort()
                d, r, c = P[0]
                queue = [(r, c)]
                num = board[r][c]
                board[r][c] = 0
                K -= visited[r][c]-1
            else:
                print(-1)
                return
        visited = [[0]*N for _ in range(N)]
        r, c = queue[0]
        visited[r][c] = 1
        while queue:
            r, c = queue.pop(0)
            if num in des.get((r, c), []):
                K += visited[r][c]-1
                queue = [(r, c)]
                break
            for dr, dc in delta:
                nr, nc = r+dr, c+dc
                if N > nr >= 0 and N > nc >= 0:
                    if visited[nr][nc] == 0 and board[nr][nc] != -1:
                        visited[nr][nc] = visited[r][c]+1
                        if visited[r][c] <= K:
                            queue.append((nr, nc))
        else:
            print(-1)
            return
    print(K)

solution()