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

https://www.acmicpc.net/problem/19238

코드

from collections import deque

n, m, fuel = map(int, input().split())
map_data = [[]]
for _ in range(n):
    map_data.append([1]+list(map(int, input().split())))
tx, ty = map(int, input().split())
customers = [[-1, -1, -1, -1]]
for i in range(1, m+1):
    sx, sy, ex, ey = map(int, input().split())
    map_data[sx][sy] = -i
    customers.append([sx, sy, ex, ey])


def get_nearest_customer(tx, ty):
    dists = []
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]

    q = deque([[tx, ty, 0]])
    visited = [[False]*(n+1) for _ in range(n+1)]
    visited[tx][ty] = True
    while q:
        x, y, d = q.popleft()
        if map_data[x][y] < 0:
            sx, sy, ex, ey = customers[-map_data[x][y]]
            dists.append([d, sx, sy, ex, ey])
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if 0 < nx <= n and 0 < ny <= n and not visited[nx][ny] and map_data[nx][ny] <= 0:
                q.append([nx, ny, d+1])
                visited[nx][ny] = True
    if not dists:
        return None
    dists.sort()
    return dists[0]


def move_to_destination(sx, sy, ex, ey):
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]

    q = deque([[sx, sy, 0]])
    visited = [[False]*(n+1) for _ in range(n+1)]
    visited[sx][sy] = True
    while q:
        x, y, d = q.popleft()
        # 승객을 태우고 목적지에 도착
        if x == ex and y == ey:
            return d
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if 0 < nx <= n and 0 < ny <= n and not visited[nx][ny] and map_data[nx][ny] <= 0:
                q.append([nx, ny, d+1])
                visited[nx][ny] = True
    return int(1e9)


for _ in range(m):
    result = get_nearest_customer(tx, ty)
    if not result:
        fuel = -1
        break
    dist, sx, sy, ex, ey = result
    fuel -= dist
    if fuel < 0:
        fuel = -1
        break
    dist = move_to_destination(sx, sy, ex, ey)
    fuel -= dist
    if fuel < 0:
        fuel = -1
        break
    fuel += dist*2
    map_data[sx][sy] = 0
    tx, ty = ex, ey

print(fuel)

 

이 코드는 아래의 2가지 단계를 M번 반복하며 택시가 M명의 승객을 모두 목적지에 데려다줄 수 있는지 확인하고 있다.

 

 

1. 택시의 현재 위치에서 최단 거리에 있는 승객 찾아가기

문제에서 제시한 태울 승객을 고르는 조건은 다음과 같다.

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

BFS를 사용하여 현재 택시의 위치로부터 모든 승객까지의 거리를 구한 뒤에 정렬하여 조건에 맞는 최단 거리의 승객을 구한다. 만약 도달할 수 있는 승객이 없다면 None을 리턴한다.

 

2. 승객을 목적지로 이동시키기

이건 일반적인 BFS를 사용해도 된다. 이동시킨 뒤에 거리를 리턴한다. 그런데 만약 이동시킬 수 없는 경우라면 충분히 큰 수(`int(1e9)`)를 리턴한다.

 

이 과정에서 중요한 것은 연료가 모자라서 승객을 태우지 못하거나 승객을 목적지로 데려다주지 못하는 경우를 잘 처리해줘야 한다는 것이다. 이것만 잘해도 금방 맞출 수 있다....