백준: 19238 스타트 택시

문제

19238번: 스타트 택시

 

문제 풀이

 문제를 단순하게 보면, 첫 번째 BFS를 탐색을 통해 택시의 위치로부터 손님의 위치까지 최단 거리를 찾는다. 그리고 두 번째 BFS 탐색을 통해 손님의 목적지까지 도달할 수 있는지를 찾는다.

 

 단순히 BFS를 두 번 생각한다고 생각하면 쉽지만 문제에 제시되는 조건들을 지켜야 한다.

1. 택시와 손님과의 거리를 찾고, 거리가 가까운 손님부터 태운다.
   • 손님이 있는 곳 까지 이동 가능한 경우
     • 거리가 같은 손님이 여러 명일 경우, `[거리, 행, 열]`을 기준으로 정렬하여 첫 번째 손님을 태운다.
   • 손님이 있는 곳 까지 이동 불가능한 경우
     • 연료가 0이 된 경우로 -1을 반환한다.
2. 손님의 목적지까지 이동 가능한지 파악한다.
   • 택시의 출발위치는 손님이 있는 위치가 된다.
   • 손님의 목적지 까지 이동 가능한 경우
     • 다음 승객을 태우기 위해, 택시의 위치가 손님의 목적지가 된다.
     • 연료는 목적지 까지 이동한 거리 * 2 만큼 충전한다.
       • 이는 현재연료 - 사용한 연료 + 이동한 거리 * 2이지만, 현재 연료 + 이동한 거리와도 같다.
   • 손님의 목적지까지 이동 불가능한 경우
     • 연료가 0이 된 경우로 -1을 반환한다.

 처음에 풀 때, `손님마다 BFS로 탐색 후 거리를 구해서 시간 초과가 발생`했다. 처음에는 다른 로직에서 시간을 잡아먹는 줄 알고 한 시간 동안 디버깅을 했는데... 도저히 못 찾겠어서 백준의 질문 답변 게시판을 참고하였다. 생각해보니, 택시 위치로부터 손님의 위치를 찾는 데는 BFS를 한 번만 돌면 되는데 왜 손님만큼 돌고 있었는가 싶었다.😂

 

코드

from sys import stdin
from collections import deque

WALL = 1


def visitable(r, c):
    return 0 <= r < N and 0 <= c < N and board[r][c] != WALL


def bfs(t_r, t_c):
    visited = [[0] * N for _ in range(N)]
    q = deque([[t_r, t_c]])
    visited[t_r][t_c] = 1

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

        for dr, dc in dirs:
            next_r, next_c = r + dr, c + dc
            if visitable(next_r, next_c) and not visited[next_r][next_c]:
                visited[next_r][next_c] = visited[r][c] + 1
                q.append((next_r, next_c))

    return visited


def find_passenger():
    dist_board = bfs(*taxi)
    p_dist = []
    for idx, info in enumerate(passengers):
        # 손님 중복 확인 방지.
        if pick_up[idx]:
            continue

        # 택시 위치를 1로 시작하므로, -1해줘야 함
        cur_dist = dist_board[info[0]][info[1]] - 1

        # 연료가 없고 방문이 불가능한 경우, 중단
        if fuel - cur_dist <= 0 or cur_dist == -1:
            print(-1)
            exit(0)
        p_dist.append([cur_dist, info[0], info[1], idx])

    # 2. 거리, R, C 순으로 리스트를 구성하였으므로 정렬하면 순차적으로 됨.
    # 가장 가까운 승객만 반환.
    return sorted(p_dist)[0]


def move_passenger(p_dist):
    global fuel, taxi

    dist, _, _, idx = p_dist
    # 가장 가까운 승객이 있는 위치로 이동
    taxi = passengers[idx][:2]
    # 승객이 있는 곳 까지 사용한 연료 감소
    fuel -= dist
    # 손님 pick up check
    pick_up[idx] = 1

    dist_board = bfs(*taxi)
    # 승객의 목적지에 도착 도달하였는지 확인
    e_r, e_c = passengers[idx][2:]
    cur_dist = dist_board[e_r][e_c] - 1

    # 연료가 없고, 방문이 불가능한 경우 중단.
    if fuel - cur_dist <= 0 or cur_dist == -1:
        print(-1)
        exit(0)

    # 택시의 시작 위치를 손님의 목적지로 변경
    taxi = [e_r, e_c]
    # 이동한 거리 * 2 만큼 연료가 충전됨.
    # 연료를 감소시키지 않고 더하면 동일한 결과
    fuel += cur_dist


if __name__ == '__main__':
    N, M, fuel = map(int, stdin.readline().split())
    board = [list(map(int, stdin.readline().split())) for _ in range(N)]
    taxi = list(map(int, stdin.readline().split()))
    # list index에 맞게 1씩 감소
    taxi = [taxi[0] - 1, taxi[1] - 1]
    passengers = [[0] for _ in range(M)]
    pick_up = [0] * M

    for idx in range(M):
        s_r, s_c, e_r, e_c = map(int, stdin.readline().split())
        # list index에 맞도록 1씩 감소
        passengers[idx] = [s_r - 1, s_c - 1, e_r - 1, e_c - 1]

    dirs = ((0, 1), (0, -1), (1, 0), (-1, 0))

    for _ in range(M):
        # 1. 택시와 손님의 거리 찾고, 조건에 적합한 승객 찾기
        cur_passenger = find_passenger()
        # 2. 손님 목적지 까지 데려다 주기
        move_passenger(cur_passenger)

    print(fuel)