문제 링크
https://www.acmicpc.net/problem/19238
🕒 Python 풀이시간: 45분
from collections import deque
dx=[0,0,-1,1]
dy=[-1,1,0,0]
n,m,fuel=map(int,input().split())
board=[list(map(int,input().split())) for _ in range(n)]
a,b=map(int,input().split())
taxi=[a-1,b-1]
clients=[]
for _ in range(m):
a,b,c,d=map(int,input().split())
clients.append((a-1,b-1,c-1,d-1))
def findClient(board,taxi,clients):
visited=[[-1]*n for _ in range(n)]
q=deque()
q.append(taxi)
visited[taxi[0]][taxi[1]]=0
while q:
now=q.popleft()
for i in range(4):
nx=now[0]+dx[i]
ny=now[1]+dy[i]
if nx<0 or ny<0 or nx>=n or ny>=n:
continue
if visited[nx][ny]!=-1:
continue
if board[nx][ny]==1:
continue
visited[nx][ny]=visited[now[0]][now[1]]+1
q.append((nx,ny))
clientList=[]
for i in range(len(clients)):
if visited[clients[i][0]][clients[i][1]]>=0:
clientList.append((visited[clients[i][0]][clients[i][1]],clients[i][0],clients[i][1],i))
if not clientList:
return False
clientList.sort()
return [clientList[0][3],clientList[0][0]]
def goDestination(board,taxi,clients,nClientIdx):
visited=[[-1]*n for _ in range(n)]
q=deque()
q.append(taxi)
visited[taxi[0]][taxi[1]]=0
while q:
now=q.popleft()
for i in range(4):
nx=now[0]+dx[i]
ny=now[1]+dy[i]
if nx<0 or ny<0 or nx>=n or ny>=n:
continue
if visited[nx][ny]!=-1:
continue
if board[nx][ny]==1:
continue
visited[nx][ny]=visited[now[0]][now[1]]+1
q.append((nx,ny))
if visited[clients[nClientIdx][2]][clients[nClientIdx][3]]==-1:
return False
return visited[clients[nClientIdx][2]][clients[nClientIdx][3]]
fail=False
while True:
result=findClient(board,taxi,clients)
if not result:
fail=True
break
nClientIdx,nCost=result
if fuel<nCost:
fail=True
break
fuel-=nCost
taxi[0],taxi[1]=clients[nClientIdx][0],clients[nClientIdx][1]
result=goDestination(board,taxi,clients,nClientIdx)
if not result:
fail=True
break
nCost=result
if fuel<nCost:
fail=True
break
taxi[0],taxi[1]=clients[nClientIdx][2],clients[nClientIdx][3]
del clients[nClientIdx]
fuel+=nCost
if not clients:
break
if fail:
print(-1)
else:
print(fuel)스마트택시 시뮬레이션: 손님 태우기와 연료 관리! 🚖⛽️
스마트택시라는 택시를 운행하는 시뮬레이션 문제이다. BFS가 많이 사용되기도 한다. 이 택시는 연료를 다루며, 중간에 연료가 떨어지거나하면 실패이므로 이에 유의하여야 한다.
먼저 손님을 태우기 위해 모든 손님까지의 최단 거리를 찾아야 한다. 그렇기 때문에 현재 택시의 위치를 기준으로 BFS를 수행하여 최단거리를 기록한다. 최단거리, 행, 열을 가지고 정렬을 수행한 후, 우리가 필요로 하는 해당 손님의 인덱스와 해당 손님까지의 거리만 return 해준다. 만약 손님이 아무도 존재하지 않는다면 즉, 손님을 다 태우지 않았는데 손님까지 갈 수 없는 경우가 존재한다면 False를 리턴하고 상황을 종료한다. 또한 가는데까지 연료가 부족해도 False를 리턴하고 상황을 종료한다.
택시와 연료를 손님을 태우는 위치와 방금 구한 손님까지의 거리를 통해 갱신한 후에 이제 목적지까지의 최단 거리를 구해준다. 똑같이 현 택시위치를 기준으로 최단거리를 구해주고 이 거리만큼 이동한다. 이 경우에도 목적지까지 가지 못하는 경우에는 False를 리턴하여 처리해준다. 이 또한 연료와 택시의 위치를 처리해주면서 택시를 이동시키고 해당 손님은 이제 고려 대상이 아니므로 리스트에서 제거한다. 이 때, 손님이 전부 존재하지 않는다면, 즉 손님을 전부 태워다드렸다면 종료한다.
이렇게 Python으로 백준의 "스마트택시" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊
