[백준 19238][python] 스타트 택시

alllloha·2021년 10월 16일
0

문제

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

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

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

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

입력

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

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

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

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

출력

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

해결방법

  1. 가장 가까운 승객을 찾는 함수 find를 생성한다
    *현재 택시 위치로부터 모든 위치까지의 거리를 측정하고 출발점에 있는 승객의 위치 중 가장 가까운 위치를 찾는다
  2. 목적지까지 이동한다
  3. 도착한 승객을 저장하는 suc 배열을 수정한다.

코드

from collections import deque

n, m, gas = map(int, input().split())

board = []
for _ in range(n):
    board.append(list(map(int, input().split())))

taxi_i, taxi_j = map(int, input().split())
taxi_i -= 1
taxi_j -= 1

start = []
end = []
for _ in range(m):
    a, b, c, d = map(int, input().split())
    start.append((a-1, b-1))
    end.append((c-1, d-1))

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

#도착한 고객을 확인하는 배열
suc = [0]*m

#가장 가까운 승객을 찾는 함수
def find():
    visit = [[-1]*n for _ in range(n)]
    queue = deque([(taxi_i, taxi_j)])
    visit[taxi_i][taxi_j] = 1

    while queue:
        r, c = queue.popleft()

        for k in range(4):
            nx = r + dx[k]
            ny = c + dy[k]

            if 0<=nx<n and 0<=ny<n and board[nx][ny] == 0 and visit[nx][ny] == -1:
                visit[nx][ny] = visit[r][c] + 1
                queue.append((nx, ny))

    #태울 승객의 위치를 담을 변수
    cus_x, cus_y = -1, -1
    customer_num = 0
    distance = n**2
    for i in range(m):
        if suc[i] == 0:
            x, y = start[i]
            if visit[x][y] == -1: #벽 때문에 목적지로 못가는 경우
                return -1, -1, -1, -1
            if visit[x][y] < distance:
                cus_x = x
                cus_y = y
                customer_num = i
                distance = visit[x][y]
            elif visit[x][y] == distance:
                if x < cus_x:
                    cus_x = x
                    cus_y = y
                    customer_num = i
                    distance = visit[x][y]
                elif x == cus_x:
                    if y < cus_y:
                        cus_x = x
                        cus_y = y
                        customer_num = i
                        distance = visit[x][y]
    
    return customer_num, cus_x, cus_y, distance-1 #탑승한 승객의 번호와 지금가지 이동한 거리를 리턴

#목적지로 승객을 데려다주는 함수
def go(customer_num):
    dist_x, dist_y = end[customer_num]
    # print(dist_x, dist_y)

    visit = [[-1]*n for _ in range(n)]
    queue = deque([(taxi_i, taxi_j)])
    visit[taxi_i][taxi_j] = 1

    while queue:
        r, c = queue.popleft()

        for k in range(4):
            nx = r + dx[k]
            ny = c + dy[k]

            if 0<=nx<n and 0<=ny<n and board[nx][ny] == 0 and visit[nx][ny] == -1:
                visit[nx][ny] = visit[r][c] + 1
                queue.append((nx, ny))

    distance = visit[dist_x][dist_y]
    return dist_x, dist_y, distance-1

cnt = 0
while True:
    num, x, y, dis = find()

    taxi_i = x
    taxi_j = y

    if num == -1 or gas - dis < 0: #데리러 갈 수 없거나 연료가 바닥난다면
        print(-1)
        break
    
    gas -= dis


    x, y, dis = go(num)
    if gas - dis < 0:
        print(-1)
        break

    gas -= dis
    gas += dis*2
    cnt+=1
    suc[num] = 1
    taxi_i = x
    taxi_j = y

    if cnt == m:
        print(gas)
        break

0개의 댓글