19238번
BFS+시뮬레이션 문제이다.
우선 문제를 간략히 정리해보자.
- m명의 손님을 태우는 것이 목표 -> 목표 미달성시 -1출력
- 택시가 가장 가까운 승객을 태워서, 해당 승객의 목적지로 데려다준다.
- 가장 가까운 승객이 여러명일 경우, 행번호가 작은 승객 그 다음으로 열번호가 가장 작은 승객을 태운다.
- 승객을 목적지로 이동시키면, 그 승객을 태워 이동하며 소모한 연료의 두배가 충전된다.(연료=거리)
- 이동중 연료가 바닥나면 실패. 단, 승객에 목적지에 도달해서 연료가 바닥난 경우는 실패로 간주하지 않음.
- 연료의 양을 구한다.
문제를 접했을 때, 생각보다 구현방법이 쉽게 나왔다. 하지만 금방 풀지는 못했다. 문제를 풀면서 자잘한 디테일들이 좀 많은 문제였다.
시나리오를 적어보겠다.
시나리오
- 입력받은 택시 시작점에서 가장 가까운 승객을 bfs로 탐색한다.
- 승객을 찾았으면, 해당 거리가 연료 사용량이므로 전체 연료에서 빼준다.(이때 연료가 0보다 적으면 실패)
- 승객의 위치를 탐색 시작점으로, 목적지를 끝점으로 설정하고, 승객의 목적지까지 다시 bfs 탐색을 한다.(이때 승객이 서있는 위치는 빈칸으로 변경)
- 목적지에 도착하면, 전체 연료에서 이동 연료를 빼주고(이때 연료가 0보다 적으면 실패), 빼준 연료의 두배를 전체 연료에 더해준다.
- 승객의 목적지를 다시 택시가 승객을 탐색하는 시작점으로 바꾸고, 2번부터 다시 반복한다.
시나리오 자체는 상당히 간단하다. 탐색을 두번만 하면 되는것이다. 이제 한번 코드를 짜보겠다.
우선 그래프상에 승객위치와 목적지를 설정하자.
승객위치, 목적지 설정
for _ in range(n):
graph.append(list(map(int, input().split())))
start_x,start_y=map(int, input().split()) #운전 시작 칸
# 주어진 좌표의 그래프는 시작점이 1부터 이므로 -1을 해준다.
start_x, start_y = start_x-1, start_y-1
for i in range(m):
#승객의 위치, 목적지에 대한 좌표를 입력받는다.
pass_fir_x,pass_fir_y,pass_end_x,pass_end_y=map(int, input().split())
graph[pass_fir_x-1][pass_fir_y-1]=(pass_end_x-1,pass_end_y-1) #승객의 위치에 목적지 좌표 삽입위와 같이 승객의 위치에 특정 수를 넣는것이 아닌, 목적지에 대한 좌표를 넣어서 해당 승객의 목적지를 별도의 탐색없이 알 수 있도록 했다.
택시가 승객을 태우러 가는 과정(BFS)
#택시가 승객을 태우러 가는 과정
def bfs(x,y,dist):
q=deque()
visited=[[0 for _ in range(n)]for _ in range(n)]
q.append([x,y,dist])
visited[x][y]=1
#가장 가까운 승객을 담는 리스트
passanger=[]
max_dist=sys.maxsize
while q:
x,y,dist=q.popleft()
#현재 거리가 max_dist 보다 크면 continue
if dist>max_dist:
continue
# x,y가 승객좌표일때
if graph[x][y]!=0 and graph[x][y]!=1: #승객의 위치에는 1과 0이 아니라 목적지 좌표가 들어있음.
passanger.append([dist,x,y])
max_dist=dist
for i in range(4):
nx=x+dx[i]
ny=y+dy[i]
if 0<=nx<n and 0<=ny<n and graph[nx][ny]!=1:
if visited[nx][ny]==0:
q.append([nx,ny,dist+1])
visited[nx][ny]=1
if passanger:
#정렬을 통해 거리가 짧고, 행이 위에있고, 열이 왼쪽에 있는 것을 정렬
return sorted(passanger)
else:
return False위에서 말했듯이, 연료사용량은 결국 이동거리이다. 따라서 이동거리를 고려해서 bfs 탐색을 하고, 가장 가까운 승객들을 passanger 리스트에 담아서 거리>x좌표>y좌표 의 우선순위를 고려하여 정렬했다.
택시 -> 승객 연료 처리
while m>0:
res=bfs(start_x,start_y,0)
#bfs 결과가 false면 승객을 못태운것이므로 -1
if not res:
print(-1)
exit()
near_pass=res[0]
use_fuel=near_pass[0]
x=near_pass[1]
y=near_pass[2]
fuel=fuel-use_fuel
#연료가 0보다 적으면 실패
if fuel<0:
print(-1)
exit()
#목적지 좌표 설정
pass_end_x, pass_end_y = (graph[x][y])[0], (graph[x][y])[1]
graph[x][y]=0 #승객 위치는 빈칸으로 변경
- m, 즉 승객의 수가 0보다 클때 while을 돌린다.
- 택시가 승객을 찾는 bfs에서 나온 결과를 보고, 실패하면 -1을 출력하고, 프로그램을 종료한다.
- 승객을 찾았다면, 반환된 리스트의 가장 앞의것(인덱스 0)을 가져와서, 연료 사용량, 목적지 좌표를 얻는다.
- 그리고 사용연료 계산을 한다. 0보다 작으면 실패이다.
- 목적지 설정을 하고, 현 승객의 위치를 빈칸(0)으로 변경한다.
승객 -> 목적지 탐색
# 승객의 목적지를 가는 과정
def move(x,y, endx,endy,dist):
q=deque()
visited=[[0 for _ in range(n)]for _ in range(n)]
q.append([x,y,dist])
visited[x][y]=1
while q:
x,y,dist=q.popleft()
if (x,y)==(endx,endy):
return dist
for i in range(4):
nx=x+dx[i]
ny=y+dy[i]
if 0<=nx<n and 0<=ny<n and graph[nx][ny]!=1:
if visited[nx][ny]==0:
q.append([nx,ny,dist+1])
visited[nx][ny]=1
승객이 목적지로 향하는 탐색은 간단하다. 시작점, 도착점이 정해진 bfs 탐색이므로 일단 bfs 탐색하듯이 해주면 된다.
반환값으로 거리를 반환해주면 된다.
승객 -> 목적지 연료처리
use_fuel=move(x,y,pass_end_x,pass_end_y,0)
#move의 결과가 false면 목적지를 도달 못했으므로 실패
if not use_fuel:
print(-1)
exit()
fuel=fuel-use_fuel
if fuel<0:
print(-1)
exit()
fuel=fuel+2*use_fuel
start_x=pass_end_x
start_y=pass_end_y
m-=1- 함수의 반환값을 받았는데, 만약 탐색을 했는데 목적지에 못도달했다면 반환값으로 None 이 나올것이다.
- 그때는 -1을 출력하고, 프로그램을 종료한다.
- 만약 도착을 했다면, 연료 처리를하고, 목적지의 좌표를 시작점으로 둔다.
- 승객은 목적지에 도착했으므로 m-1을 해준다.
전체 코드
import sys
input=sys.stdin.readline
from collections import deque
n,m,fuel=map(int, input().split()) #격자 크기, 승객 수, 연료량
graph=[]
for _ in range(n):
graph.append(list(map(int, input().split())))
start_x,start_y=map(int, input().split()) #운전 시작 칸
# 주어진 좌표의 그래프는 1부터 이므로 -1을 해준다.
start_x, start_y = start_x-1, start_y-1
for i in range(m):
pass_fir_x,pass_fir_y,pass_end_x,pass_end_y=map(int, input().split())
graph[pass_fir_x-1][pass_fir_y-1]=(pass_end_x-1,pass_end_y-1) #승객의 위치에 목적지 좌표 삽입
dx=[-1,1,0,0]
dy=[0,0,-1,1]
#택시가 승객을 태우러 가는 과정
def bfs(x,y,dist):
q=deque()
visited=[[0 for _ in range(n)]for _ in range(n)]
q.append([x,y,dist])
visited[x][y]=1
passanger=[]
max_dist=sys.maxsize
while q:
x,y,dist=q.popleft()
if dist>max_dist:
continue
# x,y가 승객좌표일때
if graph[x][y]!=0 and graph[x][y]!=1:
passanger.append([dist,x,y])
max_dist=dist
for i in range(4):
nx=x+dx[i]
ny=y+dy[i]
if 0<=nx<n and 0<=ny<n and graph[nx][ny]!=1:
if visited[nx][ny]==0:
q.append([nx,ny,dist+1])
visited[nx][ny]=1
if passanger:
return sorted(passanger)
else:
return False
# 승객의 목적지를 가는 과정
def move(x,y, endx,endy,dist):
q=deque()
visited=[[0 for _ in range(n)]for _ in range(n)]
q.append([x,y,dist])
visited[x][y]=1
while q:
x,y,dist=q.popleft()
if (x,y)==(endx,endy):
return dist
for i in range(4):
nx=x+dx[i]
ny=y+dy[i]
if 0<=nx<n and 0<=ny<n and graph[nx][ny]!=1:
if visited[nx][ny]==0:
q.append([nx,ny,dist+1])
visited[nx][ny]=1
while m>0:
res=bfs(start_x,start_y,0)
#bfs 결과가 false면 승객을 못태운것이므로 -1
if not res:
print(-1)
exit()
near_pass=res[0]
use_fuel=near_pass[0]
x=near_pass[1]
y=near_pass[2]
fuel=fuel-use_fuel
#연료가 0보다 적으면 실패
if fuel<0:
print(-1)
exit()
#목적지 좌표 설정
pass_end_x, pass_end_y = (graph[x][y])[0], (graph[x][y])[1]
graph[x][y]=0 #승객 위치는 빈칸으로 변경
use_fuel=move(x,y,pass_end_x,pass_end_y,0)
#move의 결과가 false면 목적지를 도달 못했으므로 실패
if not use_fuel:
print(-1)
exit()
fuel=fuel-use_fuel
if fuel<0:
print(-1)
exit()
fuel=fuel+2*use_fuel
start_x=pass_end_x
start_y=pass_end_y
m-=1
print(fuel)
- 문제가 엄청 어렵지는 않지만, 디테일들이 있는 문제이기 때문에 꼭 다시 풀어보도록 해야겠다.!!
Backend Developer