[백준/python] 19238번 : 스타트 택시

문제

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

택시 기사 최백준은 오늘 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을 출력한다.

 

정답

import sys
input = sys.stdin.readline

# N, M, 초기 연료 양 입력
N, M, fuel = map(int, input().split())

# 활동 영역 지도 area 입력
area = [[1 for _ in range(N+1)]]
for _ in range(N):
    area.append([1])
    area[-1].extend(list(map(int, input().split())))

# 운전을 시작하는 칸 now 입력
now = tuple(map(int, input().split()))

# 승객의 출발지와 목적지 입력
passenger = {}
for _ in range(M):
    a, b, c, d = map(int, input().split())
    passenger[(a, b)] = (c, d)

around = [(0,1), (1,0), (-1,0), (0,-1)]

take_a_taxi = False

while passenger:
    arrival, target = tuple(), set()
    visited, queue = set(), {now}
    move = 0
    
    while queue:
        candidate = set()
        for x, y in queue:
            if (0 <= x < N+1 and 0 <= y < N+1) and area[x][y] == 0:
                if take_a_taxi and (x, y) == passenger[now]:
                    del passenger[now]
                    arrival = (x, y)
                    break
                
                elif not take_a_taxi and (x, y) in passenger:
                    target.add((x, y))
                
                else:
                    for _x, _y in around:
                        if (x+_x, y+_y) not in visited:
                            candidate.add((x+_x, y+_y))
        
            visited.add((x, y))
            
        if arrival:
            take_a_taxi = False
            now = arrival
            fuel = fuel + move if fuel >= move else -1
            break

        if target:
            take_a_taxi = True
            now = sorted(target)[0]
            fuel -= move
            break
            
        if not candidate:
            fuel = -1
            break
        
        queue = candidate
        move += 1

    if fuel < 0:
        fuel = -1
        break

print(fuel)

---

# N, M, 초기 연료 양 입력
N, M, fuel = map(int, input().split())

# 활동 영역 지도 area 입력
area = [[1 for _ in range(N+1)]]
for _ in range(N):
    area.append([1])
    area[-1].extend(list(map(int, input().split())))

# 운전을 시작하는 칸 now 입력
now = tuple(map(int, input().split()))

# 승객의 출발지와 목적지 입력
passenger = {}
for _ in range(M):
    a, b, c, d = map(int, input().split())
    passenger[(a, b)] = (c, d)

around = [(0,1), (1,0), (-1,0), (0,-1)]

take_a_taxi = False

while passenger:
    arrival, target = tuple(), set()
    visited, queue = set(), {now}
    move = 0
    
    while queue:
        candidate = set()

입력을 받고 필요한 변수들을 생성한다.

 

• area : 문제에서 인덱스 1부터 시작하므로 가로, 세로 첫줄에 의미없는 1을 추가해논 후 입력받는다.
• passenger : 승객의 출발지와 목적지는 출발지 : 목적지 형태로 딕셔너리로 저장한다.
• around : 상하좌우로 이동할 때 더해지는 좌표값이다.
• take_a_taxi : 택시에 승객이 있는지 없는지 상태를 나타낸다.
• arrival : 택시에 탄 승객이 목적지에 도착했을 때 목적지 좌표를 저장한다.
• target : 같은 이동횟수 안에서 갈 수 있는 승객의 위치를 저장한다.
• visited : 이미 방문한 좌표는 방문하지 않기 위해 방문한 좌표를 저장해놓는다.
• queue : 이동해야할 곳을 저장한다.
• move : 이동횟수를 의미한다.
• candidate : 같은 이동횟수로 갈 수 있는 좌표들을 저장한다.

 

for x, y in queue:
            if (0 <= x < N+1 and 0 <= y < N+1) and area[x][y] == 0:
                if take_a_taxi and (x, y) == passenger[now]:
                    del passenger[now]
                    arrival = (x, y)
                    break
                
                elif not take_a_taxi and (x, y) in passenger:
                    target.add((x, y))
                
                else:
                    for _x, _y in around:
                        if (x+_x, y+_y) not in visited:
                            candidate.add((x+_x, y+_y))
        
            visited.add((x, y))

queue에는 같은 이동횟수로 갈 수 있는 좌표들이 들어있다.

queue에 있는 좌표를 하나씩 돌면서 인덱스 범위 내에 있으면서 벽이 아닐 때

다음 세가지 사항 중 맞는 상황에서 행동한다.

• 택시에 승객이 있고 현재 위치가 목적지라면 ->
  • passenger에서 해당 승객을 삭제한다.
  • arrival에 목적지 좌표를 저장한다.
  • 더 이상 다른 좌표를 볼 필요 없으므로 for문을 빠져나온다.
• 택시에 승객이 없고 현재 위치에 승객이 있다면 ->
  • 태울 승객 후보 target에 현재 위치를 저장한다.
• 그 외 ->
  • 상하좌우를 돌면서 방문한 적이 없는 좌표를 candidate에 저장한다.

 

현재 위치에 방문했음을 표시하기 위해 visited에 현재 위치를 추가한다.

 

        if arrival:
            take_a_taxi = False
            now = arrival
            fuel = fuel + move if fuel >= move else -1
            break

        if target:
            take_a_taxi = True
            now = sorted(target)[0]
            fuel -= move
            break
            
        if not candidate:
            fuel = -1
            break
        
        queue = candidate
        move += 1

현재 이동 횟수로 갈 수 있는 좌표를 모두 확인한 후 다음 세가지 사항을 체크한다.

• 목적지에 도착했다면 ->
  • 승객이 내림을 표시하기 위해 take_a_taxi를 False로 바꾼다.
  • now에 arrival을 저장하여 현위치를 갱신한다.
  • 연료가 움직인 것만큼 있었다면 움직인만큼 더해주고 아니면 -1로 바꾼다.
• 태울 승객 후보가 있다면 ->
  • 승객이 탔음을 표시하기 위해 take_a_taxi를 True로 바꾼다.
  • now에 태울 승객 후보 중 선택 조건에 맞는 승객의 위치를 저장하여 현위치를 갱신한다.
  • 연료를 움직인만큼 빼준다.
• 다음으로 이동할 좌표가 없다면 ->
  • 연료를 -1로 바꿔 더이상 갈 수 없음을 표시한다.

 

위 세가지 사항에 모두 맞지 않는다면

queue를 candidate로 바꾼 후 move에 1을 더해 다음으로 움직인다.