접근 과정
N x N 사이즈의 2차원 배열 내에서 “최단 경로”에 따라 태울 승객을 선택하고, 배열 내 임의의 목적지로 향해 탐색을 진행한다는 점에서 일반적인 BFS문제라고 생각하고서 접근했지만, 몇 가지 주의하지 않으면 통과할 수 없는 부분들이 있었다.
- 택시가 승객을 태우지 못할 수 있다
태울 승객을 선택하는 과정에서 택시로부터 모든 승객의 거리를 계산하는데, 이 때 벽 등으로 가로막혀서 승객을 태울 수 없는 경우가 발생한다. 매 시점 방문 처리와 이동한 거리 계산을 위한 임의의 N x N 사이즈 배열 visited에 택시로부터 모든 승객들의 거리를 저장하고, 거리 순으로 정렬하는 경우 벽에 가로막힌 승객의 좌표 값은 0이 되어버린다.(택시가 방문할 수 없는 좌표였기에, 초기 값 0이 그대로 들어간 경우)
최단 거리 순으로 정렬한 경우 택시가 해당 승객을 선택해버리는 문제가 발생한다!
- 택시와 승객이 대기하는 위치가 동일할 수 있다
택시가 처음 탐색을 진행하는 시점에 해당 위치에 이미 승객이 있는 경우를 고려하지 않고 방문하지 않은 좌표를 대상으로 탐색을 진행하는 경우, 택시와 같은 위치에 있던 승객을 찾을 수 없게 된다.
- 승객의 대기 위치와 목적지가 동일할 수 있다..
2번과 비슷한 문제이지만, 가장 생각하기 어려운 조건이었다. 아니 타자마자 내릴거면 왜 타는건데.. 타자마자 바로 내리는 경우, 이동한 거리는 0이기에 승객을 내려줌으로 추가되는 연료가 없다.
위 조건들을 유의하면서 접근한다면, 일반적인 BFS 로직으로 풀어낼 수 있다!
정리하면..
- 매 시점 택시의 위치를 기준으로 BFS를 진행해 가장 가까이 있는 승객을 찾아낸다.
(태울 수 있는 승객이 없는 경우 -1을 반환한다) - 승객들을 택시로부터의 최단 거리, 행과 열 값을 기준으로 정렬한 뒤, 첫 요소(가장 가까운 승객)의 위치로 이동한다.
(가는 중 연료가 다 떨어지는 경우 -1 반환) - 방문 처리용 배열 visited를 새로 초기화하고, 다시 BFS를 통해 승객의 목적지로 이동한다.
(연료가 다 떨어지는 경우 -1 반환) - 승객을 목적지까지 태운 경우 택시의 위치를 승객을 내려준 목적지로 변경하고, 소모한 연료의 2배를 잔여 연료량에 더한다.
- 이미 태운 승객을 다시 선택하지 않게 배열에서 제거하는 등의 과정을 진행한다.
- 이 과정을 최대 M회 반복한다.
풀이
import sys
from collections import deque
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# 택시 운전
def taxi(wasted_fuel, x, y, goal_x, goal_y):
global fuel
# 도착하기도 전에 연료를 다 써버린 경우
if wasted_fuel > fuel:
return False
# 연료 소모처리
fuel -= wasted_fuel
Q = deque()
Q.append([x, y])
while Q:
x, y = Q.popleft()
# 목적지에 도착한 경우
if x == goal_x and y == goal_y:
# 도착했지만, 남은 연료보다 더 많이 쓴 경우
if visited[x][y] > fuel:
return False
else:
fuel -= visited[x][y]
break
for _ in range(4):
tx, ty = x + dx[_], y + dy[_]
if 0 < tx <= N and 0 < ty <= N and arr[tx][ty] == 0 and not visited[tx][ty]:
visited[tx][ty] = visited[x][y] + 1
Q.append([tx, ty])
# 최단거리 승객 구하기
def distance_searching(x, y):
Q = deque()
Q.append([x, y])
while Q:
x, y = Q.popleft()
for _ in range(4):
tx, ty = x + dx[_], y + dy[_]
if 0 < tx <= N and 0 < ty <= N and arr[tx][ty] == 0 and not visited[tx][ty]:
visited[tx][ty] = visited[x][y] + 1
Q.append([tx, ty])
input = sys.stdin.readline
N, M, fuel = map(int, input().split())
arr = [[0] * (N + 1)] + [[0] + list(map(int, input().split())) for _ in range(N)]
start_x, start_y = map(int, input().split())
customers = [list(map(int, input().split())) for _ in range(M)]
fail_flag = False
# 중간에 연료가 다 떨어지는 경우는 더 이상 태울 수 없지만, 그 외에는 모든 승객을 태우게 된다.
# 이 경우, M명의 승객을 전부 태우는 것이기 때문에 최대 M회만큼 루프를 돌아야 한다.
for _ in range(M):
# 매 회차마다 택시와 승객들간의 최단거리는 달라질 수 있기에 visited를 다시 재정의
visited = [[0] * (N + 1) for _ in range(N + 1)]
distances = []
# 현재 택시 위치 기준으로 맵을 한 바퀴 다 돌면서 좌표에 대한 거리들을 구함
distance_searching(start_x, start_y)
for i in customers:
if start_x == i[0] == i[2] and start_y == i[1] == i[3]:
customers.remove(i)
break
# visited를 기반으로 승객들의 최단 거리를 구함
if customers:
for wait_x, wait_y, destination_x, destination_y in customers:
# 택시랑 승객 같은 위치에 선 경우 - 최단거리: 0
if start_x == wait_x and start_y == wait_y:
distances.append(
[0, wait_x, wait_y, destination_x, destination_y])
elif visited[wait_x][wait_y] == 0:
fail_flag = True
print(-1)
break
else:
distances.append(
[visited[wait_x][wait_y], wait_x, wait_y, destination_x, destination_y])
else:
# 최단 경로, 행, 열 순으로 정렬
distances.sort(key=lambda x: (x[0], x[1], x[2]))
# 최단거리 조회하는 과정에서 벽으로 가로막혀 승객을 태우지 못한 경우
if fail_flag: break
# 현재 위치 기준에서 승객들에 대한 거리들이 구해졌다고 생각했을 때
# 조건(최단거리, 행, 열 값) 기준으로 정렬
# 최단거리 승객 좌표 기준으로 다시 BFS 진행..
# 진입시 최단거리만큼 연료를 썼기 때문에 빼고 시작
# 여기서 연료가 이미 다 떨어진 상태라면 리턴으로 -1
visited = [[0] * (N + 1) for _ in range(N + 1)]
if taxi(*distances[0]) == False:
fail_flag = True
print(-1)
break
else:
if visited[distances[0][3]][distances[0][4]] == 0:
fail_flag = True
print(-1)
break
else:
fuel += (visited[distances[0][3]][distances[0][4]]) * 2
# 매 루프의 마지막에는 택시 위치를 바꿔줘야 함 -> 위치는 태운 승객의 도착지 위치가 될 것
start_x, start_y = distances[0][3], distances[0][4]
# 이제, 같은 승객을 또 태우러 가지 않기 위해 태운 승객을 찾아서 제외시키거나, 배열에서 제거해야 함
customer_idx = customers.index(distances[0][1:])
customers.pop(customer_idx)
if not fail_flag:
print(fuel)통과!
읽어주셔서 감사합니다!
즐거워요