[백준 19238번] 스타트 택시 (Python3)

import sys
input = sys.stdin.readline
from collections import deque
dy = [1,-1,0,0]
dx = [0,0,1,-1]

def BFS():
  cnt = 0
  fuel = K
  start = first
  while True:
    if cnt == M:
      print(fuel)
      return
    visited = [[0]*N for i in range(N)]
    dq = deque()
    dq.append((*start,0))
    distance = 1000
    passenger = M+2
    while dq:
      y,x,d = dq.popleft()
      if d>distance:
        break
      if d > fuel:
        print(-1)
        return
      if visited[y][x]:
        continue
      visited[y][x] = 1
      if board[y][x]:
        passenger = min(passenger,board[y][x])
        distance = d
        continue
      for i in range(4):
        y1,x1 = y+dy[i],x+dx[i]
        if N>y1>=0 and N>x1>=0:
          if visited[y1][x1] or board[y1][x1]==1:
            continue
          dq.append((y1,x1,d+1))
    if passenger == M+2:
      print(-1)
      return
    fuel -= distance
    ys,xs,ye,xe = startend[passenger]
    board[ys][xs] = 0
    f = taxi(ys,xs,ye,xe)
    if f>fuel or f == -1:
      print(-1)
      return
    start = (ye,xe)
    fuel += f
    cnt += 1

def taxi(ys,xs,ye,xe):
  visited = [[0]*N for i in range(N)]
  dq = deque()
  dq.append((ys,xs,0))
  while dq:
    y,x,d = dq.popleft()
    if visited[y][x]:
      continue
    visited[y][x] = 1
    if (y,x) == (ye,xe):
      return d
    for i in range(4):
      y1,x1 = y+dy[i],x+dx[i]
      if N>y1>=0 and N>x1>=0:
        if visited[y1][x1] or board[y1][x1] == 1:
          continue
        dq.append((y1,x1,d+1))
  return -1

N,M,K = map(int,input().split())

board = []
for i in range(N):
  board.append([*map(int,input().split())])

first = tuple(map(lambda x:x-1,map(int,input().split())))

data = []
startend = {}
for i in range(M):  
  data.append([*map(lambda x:x-1,map(int,input().split()))])
data.sort()
for i in range(2,M+2):
  y1,x1,y2,x2 = data[i-2]
  board[y1][x1] = i
  startend[i] = (y1,x1,y2,x2)
BFS()

아이디어는 쉬운데 반례잡기가 까다로울 수 있는 문제이다.

 

알고리즘만 설명하면,

1. 손님들의 데이터를 받아서 y,x 좌표가 작은 순으로 정렬해준다.

2. 손님들에게 2~M+1까지 번호를 매기고 각 손님들의 시작좌표를 해당 번호로 바꾼다. (1은 벽이므로)

3. 현재 위치에서 BFS로 가장 가까운 손님을 발견하면 distance를 갱신하고 번호는 작은 번호로 바꾸어준다.

4. 번호가 바뀐적이 없으면 -1을 출력

5. 바뀐적이 있으면 해당 번호 손님의 도착위치로 가는 거리를 BFS로 계산

6. 거리가 현재의 연료양보다 크면 -1 출력, 아니면 거리만큼 연료 +

7. 모든 손님을 태워주면 결과 출력

 

내가 실수한 부분은

1번에서 정렬을 하지 않고 데이터를 받는대로 번호를 매겼다.

4번의 번호가 바뀐적이 없으면 -1을 출력하지 않았다. (도착지점에 도달하지 못하면 -1을 출력하는건 처리해줬는데, 다음 손님을 발견 못하면 -1을 출력하지 않았다.)

 

 

오늘의 교훈) 항상 예외케이스를 염두하자