백준 구현 대비 스타트택시

문제 : https://www.acmicpc.net/problem/19238

접근

세가지 부분으로 도식화 하였다.
1) 가장 가까운 고객의 위치를 찾고 해당 위치로 택시를 이동시키는 함수
2) 1)에서 반환된 고객의 목적지를 찾고 해당 위치로 택시를 이동시키는 함수
3) fuel 변수에서 이동 거리만큼 뺄셈

코드

from collections import deque
movelist=[[1,0],[0,1],[-1,0],[0,-1]]



def tocustomer(di,dj):
  visited=[[0 for i in range(N)] for j in range(N)]
  visited[di][dj]=1
  
  queue=deque()
  queue.append([di,dj,0])
  tempqueue=deque()
  answer=[]
  while True:
    while queue:
      cur=queue.popleft()
      ci,cj,cd=cur[0],cur[1],cur[2]
      if graph[ci][cj]!=0:
        answer.append([ci,cj,cd])
      for mo in movelist:
        ni,nj,nd=ci+mo[0],cj+mo[1],cd+1
        if 0<=ni<N and 0<=nj<N and visited[ni][nj]==0 and graph[ni][nj]!=1:
          visited[ni][nj]=1
          tempqueue.append([ni,nj,nd])
    if(len(answer)>=1 or (not tempqueue)):
      return answer
    queue=tempqueue
    tempqueue=deque()

def todest(ci,cj):
  di,dj=graph[ci][cj][0],graph[ci][cj][1]
  visited=[[0 for i in range(N)] for j in range(N)]
  visited[ci][cj]=1
  queue=deque()
  queue.append([ci,cj,0])
  while queue:
    cur=queue.popleft()
    ci,cj,cd=cur[0],cur[1],cur[2]
    if ci==di and cj==dj:
      return cd
    for mo in movelist:
      ni,nj,nd=ci+mo[0],cj+mo[1],cd+1
      if 0<=ni<N and 0<=nj<N and visited[ni][nj]==0 and graph[ni][nj]!=1:
        queue.append([ni,nj,nd])
        visited[ni][nj]=1
  return 1e9




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

graph=[]

for i in range(N):
  graph.append(list(map(int, input().split())))

d=list(map(int, input().split()))

di,dj=d[0]-1,d[1]-1 # 운전하는 사람 위치

for j in range(M):
  c1,c2,d1,d2=list(map(int ,input().split()))
  graph[c1-1][c2-1]=[d1-1,d2-1]
  # 각 승객의 출발지에는 목적지의 정보가 담겨있음


while True:
  customlist=tocustomer(di,dj)
  if len(customlist)==0:
    break
  customlist.sort(key=lambda x:(x[2],x[0],x[1]))
  ci,cj,cd=customlist[0][0],customlist[0][1],customlist[0][2]
  if cd>fuel:
    print(-1)
    exit()
  fuel-=cd
  des=todest(ci,cj)
  if des>fuel:
    print(-1)
    exit()

  fuel-=des
  fuel+=des*2
  di,dj=graph[ci][cj][0],graph[ci][cj][1]
  graph[ci][cj]=0
  M-=1

if M==0:
  print(fuel)
else:
  print(-1)

추가

처음 제출했을 때 런타임에러(타입에러)가 발생했는데 그 이유는 todest 함수에서 목적지에 도달하지 못했을 때 none타입을 반환하기 떄문. 이로인해 밑에줄인

  if des>fuel:
    print(-1)
    exit()

부분에서 nonetype과 int의 대소관계를 비교하기 때문에 오류가 발생한 것. 이러한 오류는 해당 목적지에 도달하지 못했을 때 적당히 큰 값 (1e9)를 반환하여 해결 할 수 있었다.