19238. 스타트 택시 (Python)

 

19238번: 스타트 택시

 

풀이

 BFS를 활용한 구현 문제다. 

 처음에는 현재 택시 위치에서 모든 승객들에 대한 거리를 구해서 최소 힙에 넣어두고 문제에 주어진 조건에 따라서 먼저 태워야 하는 손님을 찾도록 구현했다. 그러다보니 매번 손님과 모든 남은 승객들의 거리를 구해야했고 아마 이 때문에 시간 초과가 발생한 것으로 보인다. 

 

 그래서 현재 택시 위치에서 BFS 탐색을 시작하여 가장 먼저 만나게 되는 승객을 찾도록 변경하였다.

 

 위의 그림은 문제에서 주어진 예제이다. 벽을 1로 표현한다고 하였으므로 승객의 번호는 임시로 -를 붙여 기록하였다. 가장 먼저 마주치는 승객을 태우면 되므로 한 번의 BFS만 진행하면 된다. 이때, 어떤 방향을 먼저 탐색할지도 중요하다. 문제에서 주어진 승객의 우선순위는 다음과 같다.

1. 최단거리가 가장 짧은 승객
2. 최단 거리가 같은 승객이 여러 명이면 행 번호가 가장 작은 승객
3. 그런 승객도 여러 명이면 열 번호가 가장 작은 승객

 그러므로 네 방향을 탐색할 때 상 -> 좌 -> 우 -> 하 순서로 탐색해야 한다. 

 

 위에서 찾은 승객을 태우고 목적지까지 이동하는 BFS를 한 번 더 수행하면 답을 구할 수 있다.

 

코드

import sys
import heapq
input = sys.stdin.readline


def isRange(x, y):
    return 0 < x <= N and 0 < y <= N


# 택시에서 가장 가까이 있는 승객을 찾기 위한 함수 
def findGuest():
    q = []
    heapq.heappush(q, (0, tx, ty))  # (이동 거리, 택시 행, 택시 열)
    visited = [[False for _ in range(N + 1)] for _ in range(N + 1)]
    visited[tx][ty] = True

    while q:
        dist, x, y = heapq.heappop(q)

        if board[x][y] < 0: # 승객을 찾았다면 
            return -board[x][y], dist # 승객 번호, 이동 거리 반환 

        for dx, dy in distArr:
            nx, ny = x + dx, y + dy

            if not isRange(nx, ny) or visited[nx][ny] or board[nx][ny] == 1:
                continue

            visited[nx][ny] = True
            heapq.heappush(q, (dist + 1, nx, ny))

    return -1, -1 # 태울 수 있는 승객을 찾지 못한 경우 


# 승객을 태우고 목적지까지 이동하는 함수 
# fx, fy : 승객의 목적지 위치 
def drive(fx, fy):
    q = []
    heapq.heappush(q, (0, tx, ty))  # (이동 거리, 택시 행, 택시 열)
    visited = [[False for _ in range(N + 1)] for _ in range(N + 1)]
    visited[tx][ty] = True

    while q:
        dist, x, y = heapq.heappop(q)

        if x == fx and y == fy:
            global fuel
            if fuel < dist: # 목적지에 도달했으나 이동 거리가 더 길어 연료가 음수가 될 경우
                return False 

            fuel += dist # 이동을 마치고 연료를 채운다.
            return True

        for dx, dy in distArr:
            nx, ny = x + dx, y + dy

            if not isRange(nx, ny) or visited[nx][ny] or board[nx][ny] == 1:
                continue

            visited[nx][ny] = True
            heapq.heappush(q, (dist + 1, nx, ny))


if __name__ == '__main__':
    N, M, fuel = map(int, input().split())
    board = [[0 for _ in range(N + 1)]]

    # 문제에서 주어진 조건대로 다음에 태울 승객을 태우기 위해 
    # 상, 좌, 우, 하 순으로 탐색해야 한다.
    distArr = [(-1, 0), (0, -1), (0, 1), (1, 0)]  # 상, 좌, 우, 하

    for _ in range(N):
        tmp = [0] + list(map(int, input().split()))
        board.append(tmp)

    # 승객의 위치 정보 
    guests = [(-1, -1, -1, -1)]  # (시작 위치 행, 시작 위치 열, 도착 위치 행, 도착 위치 열)

    tx, ty = map(int, input().split()) # 택시의 위치
    for i in range(1, M + 1):
        sx, sy, fx, fy = map(int, input().split())
        board[sx][sy] = -i # 맵에 승객의 번호를 저장 
        guests.append((sx, sy, fx, fy))

    # 모든 승객을 태우기 위해 다음의 과정을 총 M번 반복한다
    # (1) 태울 수 있는 승객을 찾는다.
    # (2) 승객을 목적지까지 태운다. 
    for _ in range(M):
        guestNo, dist = findGuest()
        if guestNo == -1: # 태울 수 있는 승객이 없을 경우 -1 출력 후 종료
            print(-1)
            sys.exit(0)

        fuel -= dist # 승객의 위치까지 이동하는데 사용된 연료를 빼준다.
        sx, sy, fx, fy = guests[guestNo]
        tx, ty = sx, sy # 택시를 승객의 위치로 이동시킨다. 

        if not drive(fx, fy): # False일 경우 승객을 목적지까지 태워줄 수 없음을 의미한다.
            print(-1)
            sys.exit(0)

        tx, ty = fx, fy # 승객을 목적지까지 이동시켰으므로 택시도 해당 위치로 이동시킨다.
        board[sx][sy] = 0 # 맵에서 해당 승객의 정보를 지워준다.

    print(fuel)