[알고리즘] 스타트 택시

포인트

• bfs 를 다룬다면 문제없이 해결할 수 있는 문제입니다. 첫번째 bfs 는 user 를 정렬하기 위한 bfs
• 2번째 bfs 는 각 점마다 최솟값을 구하기 위한 bfs 입니다. 

🧶문서는 항상 수정될 수 있습니다. 비판은 환영합니다. 

python

from collections import deque

n, m, k = map(int, input().split())
data = [list(map(int, input().split())) for _ in range(n)]

sx, sy = map(int, input().split())
sx -= 1
sy -= 1

user = [list(map(int, input().split())) for _ in range(m)]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def calc(sx: int, sy: int) -> list:
    """택시 시작점에서 정렬할 수 있도록 거리 거리 계산

    Args:
        sx (int): taxi x
        sy (int): taxi y

    Returns:
        list: 거리 계산한 배열 반환
    """
    distance = [[-1] * n for _ in range(n)]
    q = deque([(sx, sy)])
    distance[sx][sy] = 0

    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if not (0 <= nx < n and 0 <= ny < n):
                continue
            if distance[nx][ny] == -1 and data[nx][ny] == 0:
                distance[nx][ny] = distance[x][y] + 1
                q.append((nx, ny))

    return distance

def calc2(sx:int, sy:int, ex:int, ey:int) -> int:
    """최단 거리를 계산하는 함수

    Args:
        sx (int): sx
        sy (int): sy
        ex (int): ex
        ey (int): ey

    Returns:
        int: 점과 점사이 최단 거리 반환
    """
    q = deque([(sx, sy)])
    distance = [[-1]*n for _ in range(n)]
    distance[sx][sy]  = 0

    while q:
        x, y = q.popleft()

        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]

            if not(0<=nx<n and 0<=ny<n):
                continue
            if data[nx][ny] == 0 and distance[nx][ny] == -1:
                q.append((nx, ny))
                distance[nx][ny] = distance[x][y] + 1

    return distance[ex][ey]

while user:
    distance = calc(sx, sy)
    user.sort(key=lambda x: (distance[x[0] - 1][x[1] - 1], x[0], x[1]))

    ssx, ssy, ex, ey = user.pop(0)
    ssx-=1
    ssy-=1
    ex-=1
    ey-=1
    cost1 = calc2(sx, sy, ssx, ssy)
    if cost1 == -1 or k - cost1 < 0:
        print(-1)
        break
    k -= cost1
    sx, sy = ssx, ssy
    cost2 = calc2(sx, sy, ex, ey)
    if cost2 == -1 or k - cost2 < 0:
        print(-1)
        break
    k += cost2
    sx, sy = ex, ey
else:
    print(k)