자율주행 자동차
Simulation, BFS
평균 : 180'
sol : 87'43''
- 수행 시간 : 50ms
- 메모리 : 16MB
New Skills
BFS 사용시
1. 최단거리 가능 여부
2. 최단거리 길이
3. 최단거리 역추적
위 3개 확실히 숙지하자.
-> 코딩 스킬 페이지에서 다룰 예정
- 해설 study
- 튜플 비교 테크닉 -> sort를 하지 않아도 자동 비교 가능
도달이 가능한 여러 승객의 위치들 중 (거리, 행, 열) 순으로 가장 가까운 승객을 쉽게 선택하기 위해서는 tuple 형태의 비교로 쉽게 구현 가능하다. c++, python에서의 튜플은 기본적으로 첫 번째 원소 먼저 비교하고, 같으면 두 번째 원소를 비교하는 식으로 진행되기 때문에 tuple을 이용하면 우선순위가 더 높은 위치를 쉽게 구할 수 있다.return (step[best_x][best_y], best_x, best_y) > \ (step[new_x][new_y], new_x, new_y)위 코드를 보면 1번 항(거리) 먼저 비교, 두 번째로 행 비교, 마지막은 열 비교를 하여 만약 기존값의 거리가 더 멀거나, 더 아랫쪽에 있거나 더 오른쪽에 있다면 update가 true를 리턴해주게 된다.
- bfs 탐색을 할 때 2차원 배열을 더 만들기만 하면 최단거리든 역추적이든 다 가능하다.
# 1칸당 1 소비, 승객 목적지로 이동시킨 동시에 소비량 * 2 만큼 충전.
# 이동 도중 배터리가 모두 소모되면 즉시 종료.
# 승객을 목적지에 이동시킨 동시에 배터리가 모두 소모되면 배터리 충전 우선, 운행 가능.
# 마지막 승객을 태워주고 운행 종료하는 순간에도 충전 이뤄짐.
## 즉, 우선순위 : [이동] > [소비] > [충전]? > [종료 체크; if battery == 0]
# BFS 우선 순위 : 상 > 좌 > ...
##############################################################
### 도착지가 겹치는 경우 고려해야 함.
from collections import deque
n, m, c = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(n)]
car = list(map(int, input().split()))
car[0] -= 1
car[1] -= 1
clients = [list(map(int, input().split())) for _ in range(m)]
goal_map = [
[[] for _ in range(n)] for _ in range(n)
]
for row in range(m):
for col in range(4):
clients[row][col] -= 1
for row in range(n):
for col in range(n):
for num in range(m):
if row == clients[num][0] and col == clients[num][1]:
grid[row][col] = -1 * (num + 2)
goal_map[clients[num][2]][clients[num][3]].append(num + 2)
client_num = m
is_impossible = False
# 만약 그리드 안 + 도로면
def can_go(i, j):
if 0 <= i < n and 0 <= j < n:
if grid[i][j] != 1:
return True
return False
def bfs(car_pos):
global c, client_num, is_impossible
if client_num == 0:
return
q = deque()
q.append((car_pos[0], car_pos[1], 0))
visited = [[False] * n for _ in range(n)]
# 상, 좌, 하, 우
dis, djs = [-1, 0, 0, 1], [0, -1, 1, 0]
cl_list = []
cur_dis = 1000
visited[car_pos[0]][car_pos[1]] = True
# find client
while q:
ci, cj, distance = q.popleft()
# 연료 바닥나면 pass
if c - distance <= 0:
continue
# 만약 승객을 찾았다면
if grid[ci][cj] < 0 and distance <= cur_dis:
# 후보지에 추가하고 최단거리 기록
cur_dis = distance
cl_list.append([ci, cj])
# print('cl added ', cl_list)
for di, dj in zip(dis, djs):
ni, nj = ci + di, cj + dj
if can_go(ni, nj) and not visited[ni][nj]:
q.append((ni, nj, distance + 1))
visited[ni][nj] = True
if len(cl_list) == 0:
is_impossible = True
return
if cl_list:
client_num -= 1
cl_list.sort(key=lambda x: [x[0], x[1]])
# 연료 깎고
c -= cur_dis
# 차 해당 위치로 이동
car_pos[0], car_pos[1] = cl_list[0][0], cl_list[0][1]
# 목적지 설정 (-1, -2, ...)
goal = -1 * grid[cl_list[0][0]][cl_list[0][1]]
# 승객 태웠으므로 지도에서 삭제
grid[cl_list[0][0]][cl_list[0][1]] = 0
# print('pick up ', goal - 1, 'at ', car, '/ left fuel : ', c, 'goal is ', goal - 1)
# find destination
q = deque()
q.append((car_pos[0], car_pos[1], 0))
visited = [[False] * n for _ in range(n)]
visited[car_pos[0]][car_pos[1]] = True
# 상, 좌, 하, 우
dis, djs = [-1, 0, 1, 0], [0, -1, 0, 1]
while q:
ci, cj, distance = q.popleft()
if c - distance == 0:
is_impossible = True
# print('impossible, ', ci, cj, c, distance)
return
for di, dj in zip(dis, djs):
ni, nj = ci + di, cj + dj
if not can_go(ni, nj) or visited[ni][nj]:
continue
# 목적지면
for destination in goal_map[ni][nj]:
if destination == goal:
c += distance + 1
# goal_map[ni][nj] = 0
# print('arrived, fuel : ', c)
bfs([ni, nj])
return
q.append((ni, nj, distance + 1))
visited[ni][nj] = True
is_impossible = True
return
###########################################################
bfs(car)
if is_impossible:
print(-1)
else:
print(c)