BOJ - 스타트택시 19238번 (python)

❓ 문제 - 백준 스타트택시 19238번 - python 풀이법

 

출처 

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

19238번: 스타트 택시

 

📝 문제해결법

1. 이 문제는 BFS+구현으로 풀었다.

• graph 이중리스트를 이용해서 벽이 있는 부분을 -1, 아무것도 없는 부분은 -2로 변경해서 저장한다.
• cus 리스트를 이용해서 택시 고객의 현재 위치와 목적지의 위치를 저장한다.
• while문을 통해 택시를 계속 운영하는데 만약 손님이 없다면 while을 빠져나가고, 손님이 있다면 BFS로 현재 택시의 위치에서 모든 좌표로 움직이는 거리를 계산한 후, 갈 수 있는 모든 손님이 있는 위치와 거리를 찾아 move 리스트에 넣어준다.
• move 즉, 손님이 없거나 모두 다 손님까지 갈 수 없을 경우 while을 빠져나온다.
• move 리스트를 정렬하는데 (거리 내림차순 - 행 내림차순 - 열 내림차순)으로 정렬한다. 0번 인덱스, 즉 가장 가까운 손님으로 이동하기 전에 연료가 부족하면 택시 운행을 종료한다.
• 만약 손님으로 이동가능하면 다시 BFS를 돌려서 (출발-손님 현재 위치) 손님 도착 위치까지의 거리를 계산한다. 만약 갈 수 없는 곳이라면 택시 운행을 종료하고, 갈 수 있는 곳이면서 만약 연료가 부족하면 택시 운행을 종료, 연료가 충분하면 연료 - 목적지까지 거리 + 목적지까지 거리*2로 연료를 계산해준다.
• 택시 운행을 종료할 때까지 while을 돌려준 후 남은 연료를 출력한다.

2. 문제 풀면서 느낀점

• 문제 조건에 맞춰서 구현할 수 있어야한다.
• 여기서 포인트는 택시가 손님을 태우고 도착지까지 가는 거리가 0일 경우도 잘 고려해야하고, 만약 손님을 태우고 가는 거리랑 현재 연료랑 같을 경우도 택시 운행을 종료하지 않는 조건을 유념해서 풀어야한다.

 

💻 소스코드

# 스타트택시 - BOJ 19238
# BFS + 구현
import copy
from collections import deque
n, m, k = map(int, input().split())
graph = []
for i in range(n):
    data = list(map(int, input().split()))
    array = []
    for d in data:
        if d == 1:
            array.append(-1)
        else:
            array.append(-2)

    graph.append(array)

dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]
cus = []
t_x, t_y = map(int, input().split())
t_x -= 1
t_y -= 1
for _ in range(m):
    a, b, c, d = map(int, input().split())
    cus.append([a, b, c, d])

def cal_dis(graph, t_x, t_y):
    g = copy.deepcopy(graph)
    visited = [[False]*n for _ in range(n)]
    q = deque()
    q.append((t_x, t_y))
    g[t_x][t_y] = 0
    visited[t_x][t_y] = True
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 > nx or 0 > ny or nx >= n or ny >= n:
                continue
            if g[nx][ny] == -1 or visited[nx][ny] == True:
                continue
            g[nx][ny] = g[x][y] + 1
            visited[nx][ny] = True
            q.append((nx, ny))
    return g


while True:
    if k < 0:
        break
    if len(cus) == 0:
        break
    move = []
    g_copy = cal_dis(graph, t_x, t_y)
    # 택시 - 손님
    for c in cus:
        a, b, c, d = c
        dis = g_copy[a-1][b-1]
        if dis < 0:
            continue
        move.append([dis, a-1, b-1, c-1, d-1])
    if len(move) == 0:
        k = -1
        break
    else:
        move.sort(key=lambda x:(x[0], x[1], x[2]))
        # 손님 - 도착지
        if move[0][0] > k:
            k = -1
            break
        else:
            k -= move[0][0]
            t_x, t_y, a, b = move[0][1:]
            end = cal_dis(graph, t_x, t_y)
            d = end[a][b]
            if d < 0:
                k = -1
                break
            k -= d
            if k >= 0:
                k += (d*2)
                cus.remove([t_x+1, t_y+1, a+1, b+1])
                t_x, t_y = a, b
            else:
                k = -1
                break

print(k)