문제링크

19238 - 스타트택시

문제설명

N*N 크기의 격자에서 택시를 운행한다. 각 칸은 빈칸 또는 벽이고, 택시가 빈칸에 있는 경우, 상하좌우 중 빈칸인 칸으로 이동이 가능하다. 목표는 M명의 승객 태우기, 항상 최단 경로로 이동한다.승객을 태우고 목적지에 도착하면 연료가 충전되고, 연료가 바닥나면 운행을 종료한다.

승객 M명은 빈칸인 출발지에서 빈칸인 목적지로 이동하려고 한다. 한번에 한명씩만 총 M번의 운행을 해야한다.
현재 택시에서 최단거리에 위치한 승객을 먼저 탑승시킨다. 최단거리에 위치한 승객이 여러 명이면 행이 작은 순, 이런 승객도 여러 명이면 열이 작은 순으로 태운다. 승객을 태우러 이동시 한칸당 1의 연료를 소모한다.
승객을 태우고 이동하면 마찬가지로 한칸당 1의 연료 소모, 도착지에 이동을 성공하면 승객을 태우고 소모한 연료의 2배만큼 충전된다. 이동 도중에 연료를 다쓰면 운행을 종료한다.

모든 승객을 다 데려다주고 남은 연료의 양은?

문제풀이

최단거리를 찾는 문제이므로 BFS를 두번 사용하면 된다.

모든 승객을 다 태울때까지

1. 승객 고르기 (택시~승객까지의 이동)
   : BFS를 이용해서 거리가 제일 짧은 승객을 고른다.
   -> dx, dy를 상-좌-하-우 순으로 저장해서 찾은 승객이 제일 가깝고, 행번호, 열번호가 작은 승객일것이라고 생각했는데 아니었다. bfs를 돌면서 모든 승객에 대한 거리-행-열번호를 저장하고, 이를 조건에 맞게 정렬한 다음에 해당되는 승객을 return한다.

2. 승객 태우고 이동하기 (승객의 출발지~도착지까지 이동)
   : 이는 승객의 목적지에 도달할 때까지 BFS를 돌면 된다.
   승객의 목적지까지 이동이 가능하고, 연료가 충분하면 택시와 연료량을 갱신하고 승객 목록에서 해당 승객을 삭제한다.

고려해야할 부분들은
1. 승객이 있는 위치도 택시가 지날 수 있음
2. 가까운 승객 고르는 순서 !!!

전체 코드는 다음과 같다.

import sys
from collections import defaultdict, deque

input = sys.stdin.readline
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

N, M, left = map(int, input().split())
board = []
for _ in range(N):
    board.append(list(map(int, input().split())))
taxi_x, taxi_y = map(int, input().split())
taxi = [taxi_x-1, taxi_y-1]

passengers = defaultdict()
for i in range(2, M+2):
    s_x, s_y, e_x, e_y = list(map(int, input().split()))
    passengers[i] = [s_x-1, s_y-1, e_x-1, e_y-1]
    board[passengers[i][0]][passengers[i][1]] = i

def in_bound(x, y):
    if x in range(N) and y in range(N):
        return True
    return False

def find_passenger(taxi):
    queue = deque()
    queue.append([taxi[0], taxi[1], 0])
    visited = [[False for _ in range(N)] for _ in range(N)]
    possible = []

    while queue:
        x, y, c = queue.popleft()
        if board[x][y] > 1:
            # 승객이 있으면
            possible.append([c, board[x][y], x, y])

        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if in_bound(nx, ny) and board[nx][ny] != 1 and visited[nx][ny] == False:
                # 범위 안이고 빈칸이면
                queue.append([nx, ny, c+1])
                visited[nx][ny] = True
    if possible:
        return sorted(possible, key = lambda x:[x[0], x[2], x[3]])[0][:2]
    else:
        return -1, -1

def drive(passenger):
    start_x, start_y, end_x, end_y = passenger
    queue = deque([[start_x, start_y, 0]])
    visited = [[False for _ in range(N)] for _ in range(N)]

    while queue:
        x, y, c = queue.popleft()
        if x == end_x and y == end_y:
            # 목적지 도달
            return c
        
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if in_bound(nx, ny) and board[nx][ny] != 1 and visited[nx][ny] == False:
                # 범위 안이고 빈칸이면
                queue.append([nx, ny, c+1])
                visited[nx][ny] = True
    return -1

while passengers:
    # 1. 승객 고르기
    moves, i = find_passenger(taxi)

    # 2. 택시~승객까지 이동하기
    if left < moves or moves == -1:
        print(-1)
        sys.exit(0)
    start_x, start_y, end_x, end_y = passengers[i]
    taxi = [start_x, start_y]
    board[start_x][start_y] = 0
    left -= moves

    # 3. 출발지~도착지까지 이동
    moves = drive(passengers[i])
    if left < moves or moves == -1:
        print(-1)
        sys.exit(0)
    taxi = [end_x, end_y]
    left += moves # 연료 2배로 충전
    del(passengers[i])

print(left)

소요시간

1시간!