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

1. 문제  

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

택시 기사 최백준은 오늘 M명의 승객을 태우는 것이 목표이다. 백준이 활동할 영역은 N×N 크기의 격자로 나타낼 수 있고, 각 칸은 비어 있거나 벽이 놓여 있다. 택시가 빈칸에 있을 때, 상하좌우로 인접한 빈칸 중 하나로 이동할 수 있다. 알고리즘 경력이 많은 백준은 특정 위치로 이동할 때 항상 최단경로로만 이동한다.

M명의 승객은 빈칸 중 하나에 서 있으며, 다른 빈칸 중 하나로 이동하려고 한다. 여러 승객이 같이 탑승하는 경우는 없다. 따라서 백준은 한 승객을 태워 목적지로 이동시키는 일을 M번 반복해야 한다. 각 승객은 스스로 움직이지 않으며, 출발지에서만 택시에 탈 수 있고, 목적지에서만 택시에서 내릴 수 있다.

백준이 태울 승객을 고를 때는 현재 위치에서 최단거리가 가장 짧은 승객을 고른다. 그런 승객이 여러 명이면 그중 행 번호가 가장 작은 승객을, 그런 승객도 여러 명이면 그중 열 번호가 가장 작은 승객을 고른다. 택시와 승객이 같은 위치에 서 있으면 그 승객까지의 최단거리는 0이다. 연료는 한 칸 이동할 때마다 1만큼 소모된다. 한 승객을 목적지로 성공적으로 이동시키면, 그 승객을 태워 이동하면서 소모한 연료 양의 두 배가 충전된다. 이동하는 도중에 연료가 바닥나면 이동에 실패하고, 그 날의 업무가 끝난다. 승객을 목적지로 이동시킨 동시에 연료가 바닥나는 경우는 실패한 것으로 간주하지 않는다.

모든 승객을 성공적으로 데려다줄 수 있는지 알아내고, 데려다줄 수 있을 경우 최종적으로 남는 연료의 양을 출력하는 프로그램을 작성하시오.

2. 입력   

첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다.

다음 줄부터 N개의 줄에 걸쳐 백준이 활동할 영역의 지도가 주어진다. 0은 빈칸, 1은 벽을 나타낸다.

다음 줄에는 백준이 운전을 시작하는 칸의 행 번호와 열 번호가 주어진다. 행과 열 번호는 1 이상 N 이하의 자연수이고, 운전을 시작하는 칸은 빈칸이다.

그다음 줄부터 M개의 줄에 걸쳐 각 승객의 출발지의 행과 열 번호, 그리고 목적지의 행과 열 번호가 주어진다. 모든 출발지와 목적지는 빈칸이고, 모든 출발지는 서로 다르며, 각 손님의 출발지와 목적지는 다르다.

3. 출력   

모든 손님을 이동시키고 연료를 충전했을 때 남은 연료의 양을 출력한다. 단, 이동 도중에 연료가 바닥나서 다음 출발지나 목적지로 이동할 수 없으면 -1을 출력한다. 모든 손님을 이동시킬 수 없는 경우에도 -1을 출력한다.

4. 해결방법   

이 문제는 구현, BFS 문제이다. 최단거리를 구하는 문제이므로 BFS를 써야하는 문제이다. 현재위치에서 가장 가까운 승객을 탐색할때, 승객을 태우고 목적지에 최단거리로 이동할때 2가지 모두 BFS를 이용하여야하는데, 벽이 있기 때문에 최단거리를 단순계산으로 탐색할수 없기 때문이다. 보드판에 승객이 위치한 자리는 2로 표시해주었고, 승객의 위치-승객의 목적지를 key-value쌍으로 담은 딕셔너리를 생성해주어 관리하였다. 

1) next함수: 큐를 돌면서 상하좌우 보드값을 탐색하는데, 벽이 아니라면 계속 큐에 넣어주고, 승객이 있다면 승객후보군에 최단거리와 함께 저장해주면된다. 큐탐색이 끝난 후에 승객후보군들 중에서 현재위치에서 가장가까운 승객 - 행 - 열 순으로 정렬해주고, 첫번째 것만을 리턴한다. 하지만 승객후보군이 없는 경우에는 거리를 아주 큰 수로 리턴하여서 메인함수에서 더이상 승객이 없다는 것을 알수있게 해준다. 

2) move함수: 현재 택시 좌표와 승객의 목적지 좌표를 매개변수로 입력하고, 큐를 돌면서 목적지 좌표에 도착하면 큐탐색을 종료한다. 최단거리가 현재 남은 연료보다 적거나 같으면 연료를 보충해주고 True를 리턴한다. 연료가 모자라면 False를 리턴하여 메인함수에서 더이상 연료가 없다는 것을 알수있게 해준다. 

 

5) 구현코드   

from collections import deque 
n,m,oil=map(int,input().split())
board=[list(map(int,input().split())) for _ in range(n)] #활동영역 
x,y=map(int,input().split())
x,y=x-1,y-1 #현재 택시의 위치 
guest=[list(map(int,input().split())) for _ in range(m)]
dic={}
for a,b,c,d in guest:
  board[a-1][b-1]=2 #승객위치  
  dic[(a-1,b-1)]=(c-1,d-1) #승객목적지 위치 
#상하좌우 
dx=[0,0,1,-1]
dy=[1,-1,0,0]

#현재위치에서 가장가까운 승객 
def next(x,y):
  q=deque() 
  q.append((x,y,0)) #현재 택시좌표, 거리 
  visited=set((x,y)) #방문여부 
  candidate=[] #승객 후보군 
  while q:
    x,y,dis=q.popleft()
    if board[x][y]==2: #승객존재 
      candidate.append((x,y,dis)) #승객좌표, 거리 
    else:
      for d in range(4): #상하좌우탐색하면서 
        nx,ny=x+dx[d],y+dy[d]
        if 0<=nx<n and 0<=ny<n: #경계안에있고 
        #벽이 아니고 방문하지 않았으면 
          if board[nx][ny]!=1 and (nx,ny) not in visited:
            q.append((nx,ny,dis+1)) #큐에 저장 
            visited.add((nx,ny)) #방문처리 
  if candidate: #정답후보군들 정렬 (거리-행-열 순)
    candidate.sort(key=lambda x:(x[2],x[0],x[1]))
    return candidate[0]
  else: #정답후보군 없으면 
    return -1,-1,1e9 #거리 무한 리턴 

#승객 이동 
def move(x,y,gx,gy):
  global oil #남은연료
  q=deque()
  q.append((x,y,0)) #현재택시위치 
  visited=set((x,y)) #방문여부 
  min_dis=1e9 #최소거리 
  while q:
    x,y,dis=q.popleft()
    if x==gx and y==gy: #도착하면 
      min_dis=dis #최소거리 갱신 
      break
    else: #안도착하면 
      for d in range(4): #상하좌우탐색 
        nx,ny=x+dx[d],y+dy[d] 
        if 0<=nx<n and 0<=ny<n: #범위안에있고
        #벽이 아니고 방문하지 않았으면 
          if board[nx][ny]!=1 and (nx,ny) not in visited:
            q.append((nx,ny,dis+1)) #큐에 저장 
            visited.add((nx,ny)) #방문 체크 

  if min_dis<=oil:#연료가 그만큼남아있으면 
    oil+=min_dis #연료보충 
    return True 
  else: #연료 바닥남 
    return False

flag=True 
for _ in range(m):
  gx,gy,dis=next(x,y) #가까운승객 태우러가기 
  if dis<=oil: #연료안모자라면 
    board[gx][gy]=0 #승객좌표 초기화 
    oil-=dis #연료소모 
    x,y=gx,gy #현재 택시좌표 업데이트 
  else: #연료 모자람 
    flag=False
    break #종료

  nx,ny=dic[(x,y)] #승객 목적지 좌표 
  if move(x,y,nx,ny): #승객이동 가능하면
    x,y=nx,ny #현재 택시좌표 업데이트  
  else: #연료모자람
    flag=False
    break #종료
  

if flag:
  print(oil)
else:
  print(-1)

 

⭐️난이도:  골드 3 ⭐️

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

19238번: 스타트 택시