백준 알고리즘 19238번 스타트 택시 풀이 With Python

문제 링크: https://www.acmicpc.net/problem/19238

19238번: 스타트 택시

문제는 크게 2가지로 볼 수 있습니다. 첫 번째 문제는 현재 택시 위치에서 가장 가까운 손님을 태울 수 있는가? 태울 수 없다면 -1을 출력하고 태울 수 있다면 태울 손님의 위치와 연료를 계산하는 것입니다. 두 번째 문제는 손님을 태운 위치에서 목적지까지 손님을 태울 수 있는가? 없으면 -1을 출력하고 있다면, 손님을 목적지까지 태우고, 충전된 연료량을 계산하고 다시 첫 번째 문제로 돌아가는 것입니다. 저는 두 문제 모두 BFS(너비 우선 탐색)으로 해결하였습니다. 한 번에 연산하기 까다로워서  2개의 서브 함수로 문제를 해결하였습니다.  소스코드는 아래와 같습니다.

 

import sys
from collections import deque

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


def sub(bd, customer, sx, sy, fuel):
    if customer.get((sx, sy)) is not None:
        return sx, sy, fuel
    queue = deque()
    nque = deque()
    point = []
    visit = {(sx, sy): 1}
    queue.append((sx, sy))
    while 1:
        while queue:
            x, y = queue.popleft()
            for d in range(4):
                nx = x + dx[d]
                ny = y + dy[d]
                if -1 < nx < n and -1 < ny < n and bd[nx][ny] == 0 and visit.get((nx, ny)) is None:
                    visit[(nx, ny)] = 1
                    if customer.get((nx, ny)) is not None:
                        point.append((nx, ny))
                    else:
                        nque.append((nx, ny))
        fuel -= 1
        if fuel < 0:
            return -1, -1, -1
        elif point:
            if len(point) > 1:
                point.sort()
            return point[0][0], point[0][1], fuel
        else:
            queue = nque
            nque = deque()


def sub2(bd, fuel, sx, sy, tx, ty):
    if sx == tx and sy == ty:
        return 0
    queue = deque()
    visit = {(sx, sy): 1}
    queue.append((sx, sy, 0))
    while queue:
        x, y, count = queue.popleft()
        if count > fuel:
            return float('inf')
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            if -1 < nx < n and -1 < ny < n and bd[nx][ny] == 0 and visit.get((nx, ny)) is None:
                visit[(nx, ny)] = 1
                if nx == tx and ny == ty:
                    return count + 1
                queue.append((nx, ny, count + 1))
    return float('inf')


answer = 0
n, m, fuel = map(int, sys.stdin.readline().split())
board = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
gsx, gsy = map(int, sys.stdin.readline().split())
gsx -= 1
gsy -= 1
customer = {}
for _ in range(m):
    x1, y1, x2, y2 = map(int, sys.stdin.readline().split())
    customer[(x1 - 1, y1 - 1)] = [x2 - 1, y2 - 1]

while 1:
    px, py, fuel = sub(board, customer, gsx, gsy, fuel)
    if fuel < 0:
        print(-1)
        break
    tx, ty = customer[(px, py)]
    cal = sub2(board, fuel, px, py, tx, ty)
    if cal > fuel:
        print(-1)
        break
    else:
        fuel += cal
        del customer[(px, py)]
        if not customer:
            print(fuel)
            break
        gsx = tx
        gsy = ty

첫 번째 문제를 구현한 것이 sub 함수이고, 두 번째 문제를 구현한 것이 sub2함수입니다. 소스코드에 대한 질문이 있으시면 댓글 남겨주시면 답변드리겠습니다.