스타트 택시

문제 파악

• 최단거리로 승객을 태우고 목적지까지 이동해야한다.
• 주어진 연료 내에서 승객을 이동시켜야 한다.

19238번: 스타트 택시

접근 방법

BFS로 구현

1. 최단 거리로 가장 가까운 승객을 찾는다.
2. 해당 승객의 위치까지 최단거리로 이동하여 승객을 태우고, 목적지 까지 최단 거리로 이동한다.
3. 주어진 연료로 모든 승객을 이동시키고 남은 연료를 반환하거나, 이동할 수 없는 경우 -1을 반환한다.

코드 구현

from collections import deque

N, M, fuel = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]

t_x, t_y = map(int, input().split())
taxi_cord = (t_x - 1, t_y - 1)

passengers = {}
for i in range(M):
    start_x, start_y, end_x, end_y = map(int, input().split())
    passengers[(start_x - 1, start_y - 1)] = (end_x - 1, end_y - 1)

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

# 백준이 태울 승객을 고를 때는 현재 위치에서 최단거리가 가장 짧은 승객을 고른다.
# 그런 승객이 여러 명이면 그중 행 번호가 가장 작은 승객을, 그런 승객도 여러 명이면 그중 열 번호가 가장 작은 승객을 고른다.
# 택시와 승객이 같은 위치에 서 있으면 그 승객까지의 최단거리는 0이다.

def is_valid(x, y):
    return 0 <= x < N and 0 <= y < N

def pick_up(target):
    q = deque()
    t_x, t_y = target
    q.append((t_x, t_y, 0))
    visited = [[False] * N for _ in range(N)]
    candidates = []
    min_distance = float('inf')

    while q:
        cur_x, cur_y, cur_d = q.popleft()
        if cur_d > min_distance:
            break
        if (cur_x, cur_y) in passengers:
            candidates.append((cur_x, cur_y))
            min_distance = cur_d
        for i in range(4):
            n_x, n_y, n_d = cur_x + dx[i], cur_y + dy[i], cur_d + 1
            if is_valid(n_x, n_y) and board[n_x][n_y] != 1 and not visited[n_x][n_y]:
                q.append((n_x, n_y, n_d))
                visited[n_x][n_y] = True

    return candidates, min_distance

def move(target):
    q = deque()
    p_x, p_y = target
    t_x, t_y = passengers[(p_x, p_y)]
    del passengers[(p_x, p_y)]
    q.append([p_x, p_y, 0])
    visited = [[False] * N for _ in range(N)]

    while q:
        cur_x, cur_y, cur_d = q.popleft()
        if cur_x == t_x and cur_y == t_y:
            return (cur_x, cur_y), cur_d
        for i in range(4):
            n_x, n_y, n_d = cur_x + dx[i], cur_y + dy[i], cur_d + 1
            if is_valid(n_x, n_y) and board[n_x][n_y] != 1 and not visited[n_x][n_y]:
                q.append((n_x, n_y, n_d))
                visited[n_x][n_y] = True
    return (t_x, t_y), float('inf')

answer = 0

while fuel > 0 and len(passengers) != 0:
    candidates, used_fuel = pick_up(taxi_cord)
    if used_fuel > fuel or len(candidates) == 0:
        answer = -1
        break

    next_target = sorted(candidates)[0]
    fuel -= used_fuel

    taxi_cord, used_fuel = move(next_target)
    if used_fuel > fuel:
        answer = -1
        break
    fuel += used_fuel

if answer == -1:
    print(-1)
else:
    print(fuel)

배우게 된 점

항상 문제를 잘 읽고 조건을 잘 봐야한다. 백준 문제는 틀리면 반례 찾기가 어렵다. 그렇기 때문에 문제를 유심히 읽어보고 조건을 파악하여 구현을 하는 능력을 더 발전시켜야 한다.