[백준/BOJ] 19238: 스타트 택시 (Python 파이썬)

 

1. 문제 

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

 

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

 

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

 

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

 

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

 

2. 입력 

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

 

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

 

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

 

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

 

3. 출력 

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

 

4. 풀이 

구현, BFS 문제이다. 최단거리를 구하는 문제이므로 BFS를 써야하는 문제이다. 현재 위치에서 가장 가까운 승객을 탐색할 때와 목적지에 최단거리로 이동할 때 총 2번 BFS를 이용하여야 한다. 

 

5. 구현코드

from collections import deque

n,m,fuel = map(int,input().split())
board = [list(map(int,input().split())) for _ in range(n)]
x, y = map(int,input().split())
x,y = x-1,y-1 #택시 위치

client = {}
for _ in range(m):
    a,b,c,d = map(int, input().split())
    board[a - 1][b - 1] = 2  # 승객 위치
    client[(a - 1, b - 1)] = (c - 1, d - 1)  # 도착지 위치

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

# 현재 위치에서 가장 가까운 승객
def search(x,y):
    q = deque()
    q.append((x,y,0)) # x, y 위치와 거리
    visited = set((x,y)) # 방문 여부
    candidate = [] #승객 후보

    while q:
        x,y,dist = q.popleft()
        if board[x][y] == 2: #승객이 있다면 후보로 저장
            candidate.append((x,y,dist))
        else:
            for d in range(4):
                nx = x+dx[d]
                ny = y+dy[d]
                if 0<=nx<n and 0<=ny<n:
                    if board[nx][ny]!=1 and (nx,ny) not in visited:
                        q.append((nx,ny,dist+1))
                        visited.add((nx,ny))

    if candidate:
        candidate.sort(key=lambda x: (x[2],x[0],x[1])) #우선순위: 거리 → 행 번호 → 열 번호
        return candidate[0]
    else:
        return -1,-1,1e9

def move(x,y,ax,ay):
    global fuel
    q = deque()
    q.append((x,y,0)) #현재 택시 위치,거리
    visited = set((x,y))
    min_dist = 1e9

    while q:
        x,y,dist = q.popleft()
        if x==ax and y==ay:
            min_dist = dist
            break
        else:
            for d in range(4):
                nx = x + dx[d]
                ny = y + dy[d]
                if 0<=nx<n and 0<=ny<n:
                    if board[nx][ny] != 1 and (nx,ny) not in visited:
                        q.append((nx,ny,dist+1))
                        visited.add((nx,ny))

    if min_dist <= fuel:
        fuel += min_dist
        return True
    else:
        return False


flag = True
for _ in range(m):
    gx,gy,dist = search(x,y) #가장 가까운 승객 찾기
    if dist <= fuel:
        board[gx][gy] = 0
        fuel -= dist
        x,y = gx,gy
    else:
        flag=False
        break

    #목적지까지 이동
    ax, ay = client[(x,y)] #목적지 좌표
    if move(x,y,ax,ay):
        x,y = ax,ay
    else:
        flag = False
        break

if flag:
    print(fuel)
else:
    print(-1)