19238. 스타트 택시 문제 바로가기
시간 초과 에러 늪에서 한동안 허우적거린 문제!!
왜 시간 초과가 났는지
최단 경로의 손님을 찾을 때 각 손님별로 BFS를 통해 모든 최단 경로를 구했다.. (BFS를 손님의 수만큼 호출..)
따라서 최단 경로 손님을 찾을 때 BFS를 1번만 동작하도록 고쳤다!
해결 방법
문제에서 고려해야할 상황
- 도달 불가능한 승객
- 승객은 태웠는데 목적지가 도달 불가한 경우
주요 과정
최단 경로 손님 찾기 :
findPassenger함수 ★택시를 첫 좌표로 두어 bfs를 이용하여 visited에 + 1를 해주며 이동한 거리를 표시한다.
이동 좌표가 passenger_start 에 속해 있는 경우(손님이 있는 경우)
candidate(최단 경로 손님 후보 리스트)에 저장하기
minDistance 값에 이동 거리 저장하기
이후 minDistance보다 커지면 종료시키기!!! (각 손님들의 도달하는 경로 모두 구할 필요없기 때문!!)
candidate가 있는 경우 sort()로 정렬하여 태울 손님을 정한다.
없는 경우 손님들이 있어도 갈 수 가 없는 경우 → 종료 조건!
손님을 도착지에 데려다 주기 :
goDestination함수손님의 출발지 좌표와 도착지 좌표를 이용하여 bfs를 이용하여 최단 경로를 찾는다.
이때 도달하지 못하는 경우 종료시키기!!
도착지에 도달하는 경우 택시의 위치 변경해주기!!
위의 함수가 동작한 이후마다 fuel 의 값을 빼주며 도달할 수 있는지 확인한다. 0보다 작으면 종료시키도록 한다.
구현한 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
from collections import deque
def findPassenger(taxi): # 최단 경로의 손님을 찾는 함수
q = deque()
q.append(taxi)
visited = [[0] * N for _ in range(N)]
minDistance = float('inf')
candidate = [] # 최단 경로인 승객들을 저장할 리스트
while q: # BFS를 이용하여 최단 경로 탐색하기
y, x = q.popleft()
if visited[y][x] > minDistance:
break
if [y, x] in passenger_start: # 최단 경로 손님 찾기
minDistance = visited[y][x]
candidate.append([y, x])
else:
for d in range(4):
ny, nx = y + dirs[d][0], x + dirs[d][1]
if 0 <= ny < N and 0 <= nx < N and road[ny][nx] != 1 and visited[ny][nx] == 0:
visited[ny][nx] = visited[y][x] + 1
q.append([ny, nx])
if candidate:
candidate.sort() # 최단 경로, 행, 열를 기준으로 오름차순으로 정렬하기
return visited[candidate[0][0]][candidate[0][1]], candidate[0][0], candidate[0][1]
else: # 손님한테 갈 수 없는 경우
return -1, -1, -1
def goDestination(start, end): # 손님의 목적지로 가는 함수
q = deque()
q.append(start)
visited = [[0] * N for _ in range(N)]
while q: # BFS를 이용하여 최단 경로 탐색하기
y, x = q.popleft()
if [y, x] == end:
break
for d in range(4):
ny, nx = y + dirs[d][0], x + dirs[d][1]
if 0 <= ny < N and 0 <= nx < N and road[ny][nx] != 1 and visited[ny][nx] == 0:
visited[ny][nx] = visited[y][x] + 1
q.append([ny, nx])
return visited[y][x], y, x
# 입력받기
N, M, fuel = map(int, input().split())
road = [list(map(int, input().split())) for _ in range(N)]
ty, tx = map(int, input().split())
taxi = [ty - 1, tx - 1]
passenger_start = [] # 손님들의 출발지를 저장할 리스트
passenger_end = [] # 손님들의 도착지를 저장할 리스트
for _ in range(M):
sy, sx, ey, ex = map(int, input().split())
passenger_start.append([sy - 1, sx - 1])
passenger_end.append([ey - 1, ex - 1])
dirs = [[1, 0], [0, 1], [-1, 0], [0, -1]]
for _ in range(M):
distance, py, px = findPassenger(taxi) # 최단 경로의 손님을 찾는 함수
if distance == -1 or fuel - distance < 0: # 손님에게 못가거나 연료가 떨어지는 종료조건
fuel = -1
break
fuel -= distance # 손님한테 가는 길에 사용한 연료 계산하기
idx = passenger_start.index([py, px]) # 최단 경로의 손님의 인덱스 찾기
passenger_start[idx] = [-1, -1] # 손님을 태웠기에 findPassenger에서 제외되기 위해 [-1, -1]로 설정하기
distance2, py2, px2 = goDestination([py, px], passenger_end[idx]) # 손님의 목적지로 가는 함수
if [py2, px2] != passenger_end[idx] or fuel - distance2 < 0: # 도착지에 도달하지 못하거나 연료가 떨어지는 종료조건
fuel = -1
break
# 손님을 도착지에 잘 데려다준 경우
fuel += distance2 # 도착지까지 연료를 - distance 사용하고 충전이 + distance * 2 이기에 최종적으로 + distance하기
taxi = [py2, px2] # 택시 위치 갱신하기
print(fuel)