[Programmers] Level 2. 충돌위험 찾기

🔗 Problem Link

프로그래머스

---

❔Thinking

• 2차원 배열로 주어진 위치에서, 각 로봇이 주어진 위치로 최단 경로를 통해 이동한다.
• 로봇이 해당 위치를 지날 때, 또 다른 로봇이 동일한 위치를 지난다면 충돌 위험으로 생각한다.
• 모든 로봇이 정해진 포인트를 모두 이동할 때, 몇번의 충돌 위험이 있는지 반환한다.
• 행을 먼저 이동하고, 그 다음으로 열을 이동한다.
• routes는 i+1번째 로봇이 가야할 경로를 나타낸다 (ex - [2,3,4,5]는 2포인트에서 3으로, 3에서 4로, 4에서 5로 이동한다)

---

💻Solution

from collections import defaultdict
def solution(points, routes):
    points_by_time = defaultdict(list)
    
    for idx, route in enumerate(routes):
        time = 0
        # 초기 위치
        points_by_time[(time, points[route[0]-1][0], points[route[0]-1][1])].append(idx+1)
        for i in range(1, len(route)):
            now_r, now_c = points[route[i-1]-1]
            e_r, e_c = points[route[i]-1]


            # 행 이동
            if now_r > e_r: # 위로 이동
                for i in range(now_r-1, e_r-1, -1):
                    time += 1
                    points_by_time[(time, i, now_c)].append(idx+1)
            elif now_r < e_r: # 아래로 이동
                for i in range(now_r+1, e_r+1):
                    time += 1
                    points_by_time[(time, i, now_c)].append(idx+1)

            # 열 이동
            if now_c > e_c: # 왼쪽으로 이동
                for i in range(now_c-1, e_c-1, -1):
                    time += 1
                    points_by_time[(time, e_r, i)].append(idx+1)
            elif now_c < e_c: # 오른쪽으로 이동
                for i in range(now_c+1, e_c+1):
                    time += 1
                    points_by_time[(time, e_r, i)].append(idx+1)
    
    # 각 시간별 위치가 중복된다면, 충돌 위험
    crash_cnt = 0
    for value in points_by_time.values():
        if len(value) >= 2:
            crash_cnt += 1
    return crash_cnt

---

🗝️keypoint

1. 해당 시간에 해당 위치를 지나는 로봇을 파악해야 하기 때문에, 좌표별 시간별 확인 도구가 필요하다.
2. 각 로봇의 시작은 이전 위치의 도착과 같기 때문에, 매 이동마다 시작 위치를 저장한다면 중복으로 저장될 수 있다.