[Python | 프로그래머스 | Lv_2] 충돌위험 찾기 (PCCP 기출문제)

😉 아이디어

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