[백준] 19238번 - 스타트 택시 (파이썬)

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

 

# 스타트 택시
from collections import deque
import sys
input = sys.stdin.readline

N, M, fuel = map(int, input().split())

# 지도
arr = [[]]
for _ in range(N):
    arr.append([0]+list(map(int, input().split())))

# 현재 위치
taxi = list(map(int, input().split()))

# 사람들 정보
people = []
for _ in range(M):
    people.append(list(map(int, input().split())))

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


def find_person():
    tx, ty = taxi
    dist_map = get_dist(tx, ty)
    people.sort(key=lambda p: (-dist_map[p[0]][p[1]], -p[0], -p[1]))
    sx, sy, ex, ey = people.pop()
    return [sx, sy, ex, ey, dist_map[sx][sy]]


def drive():
    global taxi
    global fuel
    # 픽업
    sx, sy, ex, ey, dist = find_person()
    if dist == -1:
        return False
    fuel -= dist
    if fuel < 0:
        return False
    # 픽아웃
    used = get_dist(sx, sy)
    if used[ex][ey] == -1:
        return False
    fuel -= used[ex][ey]
    if fuel < 0:
        return False
    fuel += used[ex][ey]*2
    taxi = [ex, ey]
    return True


def get_dist(a, b):
    q = deque()
    q.append((a, b))
    visited = [[-1 for _ in range(N+1)] for _ in range(N+1)]
    visited[a][b] = 0
    while q:
        x, y = q.popleft()
        for k in range(4):
            nx = x+dx[k]
            ny = y+dy[k]
            if 0 < nx <= N and 0 < ny <= N and visited[nx][ny] == -1:
                if not arr[nx][ny]:
                    visited[nx][ny] = visited[x][y]+1
                    q.append((nx, ny))
    return visited


for _ in range(M):
    if not drive():
        fuel = -1
        break

print(fuel)

 

BFS, 구현(시뮬레이션)
1. 입력을 전부 받아온다.
2. drive : 운전을 시작해서 가까운 사람을 픽업, 픽아웃이 가능하면 True 불가능하면 False 반환
    - find_person : 가장 가까운 사람의 정보를 반환
        - 정렬을 통해 거리가 가장 가까우면서 행과 열의 크기가 가장 작은 사람을 pop
        - 이후 해당 거리와 함께 반환
    - get_dist : bfs를 통해서 특정 위치에서 다른 위치들까지의 거리정보를 반환
    - 픽업 : 현재 위치에서 가장 가까운 사람까지 이동
    - 픽아웃: 사람을 픽업하고 현재 위치에서 목적지까지 이동
    - 도중에 기름이 0이 되면 return False
    - 갈 수 없을 시에도 return False
    - 그 외, 기름을 사용한 값의 두배로 충전해주고 택시의 위치 업데이트, return Ture

 

구현(시뮬렝이션)이다. 그냥 문제에서 지시한 대로 풀어나갔다.

도중에 bfs를 여러 번 하는 게 신경 쓰였지만 시간 복잡도가 괜찮을 것 같아서 그냥 풀었다.

 

문제를 요약하면

가장 가까운 사람을 고르고, 해당 사람을 픽업하면서 연료 소모

해당 사람의 목적지까지 이동을 하고, 그때 사용한 연료의 두배를 충전

도중에 연료가 떨어지지 않고 모든 사람을 픽업 / 픽아웃 시 남은 연료 출력