728x90
😉 아이디어
1. 최소 이동거리 간 이동경로를 모두 저장 👉 장애물이 없기 때문에 문제에서 제시한 _!rows!_ 부터 맞추고 _!cols!_ 를 맞추면 된다.
2. 산출된 이동경로를 순회하며 같은 시간(인덱스)에 충돌하는 로봇의 지점 위치를 계산
😉 풀이
from collections import deque
from collections import defaultdict
def solution(points, routes):
answer = 0
rows, cols = 0, 0
for point in points:
rows = max(rows, point[0])
cols = max(cols, point[1])
grid = [[0] * cols for _ in range(rows)]
for point in points:
grid[point[0] - 1][point[1] - 1] = 1
all_paths = []
for route in routes:
all_paths.append(min_route(route, points))
answer = overlap_count(all_paths)
return answer
def overlap_count(all_paths):
result_count = 0
max_path_length = max(len(path) for path in all_paths)
for i in range(max_path_length):
count_dict = defaultdict(int)
for path in all_paths:
if i >= len(path):
continue
count_dict[path[i]] += 1
for key, count in count_dict.items():
if count > 1:
result_count += 1
return result_count
def min_route(route, points):
path = []
for i in range(len(route) - 1):
start_x, start_y = points[route[i] - 1]
end_x, end_y = points[route[i + 1] - 1]
while start_x != end_x:
path.append((start_x, start_y))
start_x += 1 if start_x < end_x else -1
while start_y != end_y:
path.append((start_x, start_y))
start_y += 1 if start_y < end_y else -1
path.append((start_x, start_y))
return path✔️링크 : https://school.programmers.co.kr/learn/courses/30/lessons/340211
