[백준/파이썬] 19238. 스타트 택시

# [Gold II] 스타트 택시 - 19238 [문제 링크](https://www.acmicpc.net/problem/19238) ### 성능 요약 메모리: 112144 KB, 시간: 168 ms ### 분류 구현, 그래프 이론, 그래프 탐색, 시뮬레이션, 너비 우선 탐색, 격자 그래프 ### 제출 일자 2025년 11월 11일 16:40:03 ### 문제 설명

스타트링크가 "스타트 택시"라는 이름의 택시 사업을 시작했다. 스타트 택시는 특이하게도 손님을 도착지로 데려다줄 때마다 연료가 충전되고, 연료가 바닥나면 그 날의 업무가 끝난다.

택시 기사 최백준은 오늘 M명의 승객을 태우는 것이 목표이다. 백준이 활동할 영역은 N×N 크기의 격자로 나타낼 수 있고, 각 칸은 비어 있거나 벽이 놓여 있다. 택시가 빈칸에 있을 때, 상하좌우로 인접한 빈칸 중 하나로 이동할 수 있다. 알고리즘 경력이 많은 백준은 특정 위치로 이동할 때 항상 최단경로로만 이동한다.

M명의 승객은 빈칸 중 하나에 서 있으며, 다른 빈칸 중 하나로 이동하려고 한다. 여러 승객이 같이 탑승하는 경우는 없다. 따라서 백준은 한 승객을 태워 목적지로 이동시키는 일을 M번 반복해야 한다. 각 승객은 스스로 움직이지 않으며, 출발지에서만 택시에 탈 수 있고, 목적지에서만 택시에서 내릴 수 있다.

백준이 태울 승객을 고를 때는 현재 위치에서 최단거리가 가장 짧은 승객을 고른다. 그런 승객이 여러 명이면 그중 행 번호가 가장 작은 승객을, 그런 승객도 여러 명이면 그중 열 번호가 가장 작은 승객을 고른다. 택시와 승객이 같은 위치에 서 있으면 그 승객까지의 최단거리는 0이다. 연료는 한 칸 이동할 때마다 1만큼 소모된다. 한 승객을 목적지로 성공적으로 이동시키면, 그 승객을 태워 이동하면서 소모한 연료 양의 두 배가 충전된다. 이동하는 도중에 연료가 바닥나면 이동에 실패하고, 그 날의 업무가 끝난다. 승객을 목적지로 이동시킨 동시에 연료가 바닥나는 경우는 실패한 것으로 간주하지 않는다.

<그림 1>

<그림 1>은 택시가 활동할 영역의 지도를 나타내며, 택시와 세 명의 승객의 출발지와 목적지가 표시되어 있다. 택시의 현재 연료 양은 15이다. 현재 택시에서 각 손님까지의 최단거리는 각각 9, 6, 7이므로, 택시는 2번 승객의 출발지로 이동한다.

<그림 2>

<그림 3>

<그림 2>는 택시가 2번 승객의 출발지로 가는 경로를, <그림 3>은 2번 승객의 출발지에서 목적지로 가는 경로를 나타낸다. 목적지로 이동할 때까지 소비한 연료는 6이고, 이동하고 나서 12가 충전되므로 남은 연료의 양은 15이다. 이제 택시에서 각 손님까지의 최단거리는 둘 다 7이므로, 택시는 둘 중 행 번호가 더 작은 1번 승객의 출발지로 이동한다.

<그림 4>

<그림 5>

<그림 4>와 <그림 5>는 택시가 1번 승객을 태워 목적지로 이동시키는 경로를 나타낸다. 남은 연료의 양은 15 - 7 - 7 + 7×2 = 15이다.

<그림 6>

<그림 7>

<그림 6>과 <그림 7>은 택시가 3번 승객을 태워 목적지로 이동시키는 경로를 나타낸다. 최종적으로 남은 연료의 양은 15 - 5 - 4 + 4×2 = 14이다.

모든 승객을 성공적으로 데려다줄 수 있는지 알아내고, 데려다줄 수 있을 경우 최종적으로 남는 연료의 양을 출력하는 프로그램을 작성하시오.

### 입력

첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N², 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다.

다음 줄부터 N개의 줄에 걸쳐 백준이 활동할 영역의 지도가 주어진다. 0은 빈칸, 1은 벽을 나타낸다.

다음 줄에는 백준이 운전을 시작하는 칸의 행 번호와 열 번호가 주어진다. 행과 열 번호는 1 이상 N 이하의 자연수이고, 운전을 시작하는 칸은 빈칸이다.

그다음 줄부터 M개의 줄에 걸쳐 각 승객의 출발지의 행과 열 번호, 그리고 목적지의 행과 열 번호가 주어진다. 모든 출발지와 목적지는 빈칸이고, 모든 출발지는 서로 다르며, 각 손님의 출발지와 목적지는 다르다.

### 출력

모든 손님을 이동시키고 연료를 충전했을 때 남은 연료의 양을 출력한다. 단, 이동 도중에 연료가 바닥나서 다음 출발지나 목적지로 이동할 수 없으면 -1을 출력한다. 모든 손님을 이동시킬 수 없는 경우에도 -1을 출력한다.

 

import heapq

di = [-1, 1, 0, 0]
dj = [0, 0, -1, 1]

def find_passenger(ti, tj) :
    global board, fuel
    N = len(board)
    q = []
    visited = [[0] * N for _ in range(N)]

    heapq.heappush(q, (0, ti, tj))  # 우선순위: 거리, 행, 열
    visited[ti][tj] = 1

    while q :
        curr, ci, cj = heapq.heappop(q)

        if curr > fuel :    # 현재 소모한 연료가 충전되어 있는 연료보다 많다면
            return -1

        if board[ci][cj] < 0 :  # 승객이 서있는 자리라면
            return ci, cj, curr

        for d in range(4) :
            ni, nj = ci + di[d], cj + dj[d]
            if 0<=ni<N and 0<=nj<N and visited[ni][nj] == 0 :
                if board[ni][nj] <= 0 : # 다른 승객이 있는 자리도 포함
                    heapq.heappush(q, (curr+1, ni, nj))
                    visited[ni][nj] = 1

    # 그럼에도 불구하고 도달하지 못했다면...
    return -1

def move_passenger(si, sj, ei, ej) :
    global board, fuel
    N = len(board)
    q = []
    visited = [[0] * N for _ in range(N)]

    q.append((0, si, sj))
    visited[si][sj] = 1

    while q :
        curr, ci, cj = q.pop(0)

        if curr > fuel :    # 도착지 전에 연료가 모두 소모됨
            return -1

        if (ci, cj) == (ei, ej) :   # 도착지에 잘 도착했다면
            return curr

        for d in range(4) :
            ni, nj = ci + di[d], cj + dj[d]
            if 0<=ni<N and 0<=nj<N and visited[ni][nj] == 0 :
                if board[ni][nj] <= 0 :
                    q.append((curr+1, ni, nj))
                    visited[ni][nj] = 1

    return -1

def main() :
    """
    손님을 도착지로 데려다 주면 연료가 충전된다.
    이동할 때마다 연료는 1씩 소모
    승객을 태운 후 도착지로 가면 소모한 연료의 두 배 만큼 충전된다.
    => 도착지에 도착했을 때 연료가 0 이상이면 사용한 연료만큼 충전?
    => 이동하는 도중에 음수로 전환되면 return -1 인게 더 나은감?

    M명의 승객을 태워야 함. 그렇지 않으면 return -1
    먼저 태울 승객은 현재 택시의 위치에서 가장 가까운 승객, 가장 작은 행번호, 가장 작은 열번호 순
    """
    global board, fuel
    N, M, fuel = map(int, input().split())
    board = [list(map(int, input().split())) for _ in range(N)]
    ti, tj = map(int, input().split())  # 택시 시작 위치
    ti, tj = ti-1, tj-1
    destinations = []
    for i in range(1, M+1) :
        si, sj, ei, ej = map(int, input().split())
        board[si-1][sj-1] = -i  # 승객 번호
        destinations.append((ei-1, ej-1))

    passengers = M

    while passengers > 0 :  # M명 태우기를 원하니까
        res = find_passenger(ti, tj)    # 승객 찾기

        if res == -1 :  # 연료가 다 소모되었거나, 다음 승객을 태울 수 없는 상황일 경우
            return -1

        ti, tj, cost = res  # 택시가 승객의 위치까지 이동
        fuel -= cost    # 승객의 위치까지 이동하는데 소모된 연료

        # 승객을 태움
        person = -board[ti][tj] - 1     # 현재 탑승한 승객 정보를 받아온다.
        board[ti][tj] = 0   # 태운 승객 위치는 0으로 갱신
        
        # 승객을 태운 택시가 도착지 까지 이동
        cost = move_passenger(ti, tj, destinations[person][0], destinations[person][1])
        
        # 도달하지 못했으면
        if cost == -1 :
            return -1
        
        # 도착지까지 도착한 택시의 위치 및 연료 충전
        ti, tj = destinations[person][0], destinations[person][1]
        fuel += cost
        
        # 승객은 내린다. 
        passengers -= 1

    return fuel

if __name__ == "__main__" :
    print(main())

문제가 굉장히 어려웠다. 기존에 풀어봤던 BFS 문제와 조금 다른 문제라서 손도 못 대봤다. 다른 분들의 코드를 많이 참고 하였다. 

우선 main 함수 부터 살펴보자

• 입력: 입력 받을 때 주의할 점은 주어진 택시, 승객 좌표들이 1-index 가 되어있기 때문에 0-index로 바꾸는 것이 중요하다.
• passengers = M : 이거 그냥 M 해도 될텐데, 원본 데이터를 손상시키기 싫어서 이렇게 새로 받아서 수행하였다. 
• while : 모든 passenges 를 귀가(?)시키는 것이 목적. 아마 모두 귀가 시킬 수 없다면 나머지 두 함수 중 하나에서 -1을 return 할 것이기 때문에 이 부분에 대해서는 걱정할 필요 없을 것이다.
• while loop 에서는 그냥 문제에서 주어진 대로 차근히 구현하면 된다. (난 못했다.)
  • 빈 택시가 승객을 태우러 가는 res 부분.
  • 승객을 태운 택시가 도착지까지 가는 cost 부분.
  • 승객 내리기.
• 정답 처리. 

find_passenger 함수 : 빈 택시가 승객을 태우러 가는 함수

• 승객을 탑승시키는 우선순위(거리, 행, 열) 이 존재하기 때문에 우선순위 큐, 힙을 활용하기로 하였다. 
• 우선순위 큐와 방문 배열을 생성하고 초기값을 받아온다. 
• while loop
  • 우선순위에 따라 값을 받아온다. 
  • 미리 여기서 정답처리를 해놓고 가는 것이 편하여 여기서 모든 정답처리를 진행하였다.
    • 도달하기 전에 이미 채워져 있는 연료보다 소모된 연료가 많으면 => -1
    • 현재 위치가 승객이 서 있는 위치라면 => 위치 정보와 소모된 연료 
  • 아직 승객을 찾지 못한 경우, 네 조건(네 방향, 범위내, 미방문, 조건: 벽이 아니라면) 검사 후 우선순위 큐에 현재 소모된 연료+1, 다음 행, 다음 행을 넣고 방문처리
• 모든 자리가 지나갈 수 없거나 방문을 하였다면 이때는 갈 수 없는 곳에 승객이 있기 때문에 -1을 반환한다. 여기서 모두 귀가(?) 시킬 수 없을 때의 경우를 제한할 수 있다.

move_passenger 함수 : 승객을 태운 택시가 도착지로 향하는 함수

• 여기서는 deque를 활용하는 것이 더 나을 것이다. 그러나 list에서도 pop(0)을 하게 되면 deque.popleft()와 같은 효과를 볼 수 있기 때문에 그냥 구현하였다. 
• 일반 큐와 방문 배열을 생성하고 초기값을 입력. => 이미 find에서 우선순위로 정렬한 후 우선순위에 따른 승객을 정렬하였기 때문에 도착 위치도 자연스레 우선순위에 따라 정렬이 되었다. 이는 main 함수에서 확인하면 된다. 
• while loop
  • pop(0) 을 함으로써, BFS 를 진행한다. 
  • 현재 값을 받아오면 바로 정답처리를 진행
    • 도착지에 도달하기 전, 채워져 있는 연료보다 소모된 연료가 많으면 => -1. 이때 도착하였을 때 연료가 0이라도 괜찮다고 문제에 나와 있으니 부등호에 신경을 써야 한다. 
    • 현재 위치가 도착 지점이라면(ei, ej) => 현재 소모된 연료 값을 return 한다. 
  • 정답처리가 되지 않았다면, 네 조건(네 방향, 범위내, 미방문, 조건: 벽이 아니라면) 검사 후 큐에 다음 값을 저장, 방문처리
• 여기서도 역시 도착지에 갈 수 없는 상황이라면, return -1. 이 역시도 모두 귀가(?) 시킬 수 없을 떄의 경우를 제한할 수 있다. 

이 문제를 풀면서 2번의 BFS, 하나는 우선순위 큐를 활용, 하나는 deque를 활용하는 2번의 BFS를 거치고 한 후 정답 처리 까지 신경써야 할 부분이 많은 문제였다. 이 문제를 계기로 이런 구현, 시뮬레이션 문제나 고도화된 그래프 문제를 건드려봐야겠다.