[백준] 19238 - 스타트 택시 (파이썬, Python)

https://pixabay.com/ko/photos/우산-햇빛-여자-비-빛-6239364/

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

19238번: 스타트 택시

 

해당 문제는 그래프 문제입니다.

문제의 목표는 주어진 모두 승객들을 목적지까지 이동시킨 후 남아 있는 연료를 구하는 것입니다.

단, 택시가 이동하는 중 연료가 바닥이 나거나 승객을 목적지까지 이동시킬 수 없다면 -1을 출력합니다.

 

이 문제는 두 가지 중요한 조건이 있다고 생각합니다.

조건 1. 다음에 태울 승객을 정할 때는 최단 거리에 있는 승객을 태운다.

조건 2. 최단 거리에 있는 승객(거리가 같은 승객)이 둘 이상이라면 낮은 행에 있는 승객을, 행 또한 같으면 낮은 열에 있는 승객을 태운다.

 

조건 1에 의해서 해당 문제는 bfs(너비 우선 탐색)로 해결해야 하는 걸 알 수 있습니다.

 

조건 2에 의해서 bfs를 통해 같은 거리에 있는 승객을 발견했을 때 행과 열을 비교해야 합니다.

문제를 처음 풀 때 탐색 방향을 '상 -> 좌 -> 우 -> 하' 순서로 지정하면 해당 조건을 만족할 줄 알았지만 틀렸습니다.

전에도 이런 실수를 몇 번 한 거 같은데, 이런 조건을 만난다면 따로 처리해줘야 할 거 같아요😅

'조건 2'는 단순 조건문이 아닌 우선순위 큐를 이용해서 해결했습니다.

 

전체 코드

제출 언어: Python3

시간: 256ms

import sys
from collections import deque
import heapq

def findPassenger():
    global  fuel, tr, tc, mat, dx, dy
    priorque = []
    que = deque([(tr, tc, 0)])
    visited = [ [False] * N for _ in range(N)]
    visited[tr][tc] = True
    passengerId = -1
    minD = float('inf')

    while que:
        cr, cc, cd = que.popleft()

        if mat[cr][cc] >= 2 and minD >= cd:
            heapq.heappush(priorque, (cr, cc))
            minD = cd
            
        elif minD < cd:
            continue

        for idx in range(4):
            nr, nc = cr+dy[idx], cc+dx[idx]
            if 0 <= nr < N and 0 <= nc < N and mat[nr][nc] != 1 and not visited[nr][nc]:
                visited[nr][nc] = True
                que.append((nr, nc, cd+1))

    if len(priorque) > 0:
        pr, pc = heapq.heappop(priorque)
        tr, tc = pr, pc
        passengerId = mat[pr][pc]-2
        mat[pr][pc] = 0

    fuel -= minD
    return passengerId

def goToDestination(dr, dc):
    global  fuel, tr, tc, mat, dx, dy
    que = deque([(tr, tc, 0)])
    visited = [ [False] * N for _ in range(N)]
    visited[tr][tc] = True
    minD = float('inf')

    while que:
        cr, cc, cd = que.popleft()

        if cr == dr and cc == dc:
            minD = cd
            tr, tc = dr, dc
            break
        
        for idx in range(4):
            nr, nc = cr+dy[idx], cc+dx[idx]
            if 0 <= nr < N and 0 <= nc < N and mat[nr][nc] != 1 and not visited[nr][nc]:
                visited[nr][nc] = True
                que.append((nr, nc, cd+1))

    fuel -= minD
    return minD
    

if __name__ == "__main__":
    N, M, fuel =  map(int, sys.stdin.readline().strip().split())
    mat = [ list(map(int, sys.stdin.readline().strip().split())) for _ in range(N) ]
    tr, tc = map(int, sys.stdin.readline().strip().split())
    tr, tc = tr -1 ,tc - 1
    destinations = []

    dx = [0, -1, 0, 1]
    dy = [-1, 0, 1, 0]

    for idx in range(M):
        pr, pc, dr, dc = map(int, sys.stdin.readline().strip().split())
        mat[pr-1][pc-1] = idx+2
        destinations.append((dr-1, dc-1))

    while M > 0:
        pid = findPassenger()
        M -= 1

        if fuel <= 0:
            fuel = -1
            break

        dr, dc = destinations[pid]
        d = goToDestination(dr, dc)

        if fuel < 0:
            fuel = -1
            break

        fuel += d*2

    print(fuel)