[프로그래머스 / PCCP 기출문제 3번 / Python] 충돌위험 찾기

문제

어떤 물류 센터는 로봇을 이용한 자동 운송 시스템을 운영합니다. 운송 시스템이 작동하는 규칙은 다음과 같습니다.

1. 물류 센터에는 (r, c)와 같이 2차원 좌표로 나타낼 수 있는 n개의 포인트가 존재합니다. 각 포인트는 1~n까지의 서로 다른 번호를 가집니다.
2. 로봇마다 정해진 운송 경로가 존재합니다. 운송 경로는 m개의 포인트로 구성되고 로봇은 첫 포인트에서 시작해 할당된 포인트를 순서대로 방문합니다.
3. 운송 시스템에 사용되는 로봇은 x대이고, 모든 로봇은 0초에 동시에 출발합니다. 로봇은 1초마다 r 좌표와 c 좌표 중 하나가 1만큼 감소하거나 증가한 좌표로 이동할 수 있습니다.
4. 다음 포인트로 이동할 때는 항상 최단 경로로 이동하며 최단 경로가 여러 가지일 경우, r 좌표가 변하는 이동을 c 좌표가 변하는 이동보다 먼저 합니다.
5. 마지막 포인트에 도착한 로봇은 운송을 마치고 물류 센터를 벗어납니다. 로봇이 물류 센터를 벗어나는 경로는 고려하지 않습니다.

이동 중 같은 좌표에 로봇이 2대 이상 모인다면 충돌할 가능성이 있는 위험 상황으로 판단합니다. 관리자인 당신은 현재 설정대로 로봇이 움직일 때 위험한 상황이 총 몇 번 일어나는지 알고 싶습니다. 만약 어떤 시간에 여러 좌표에서 위험 상황이 발생한다면 그 횟수를 모두 더합니다.

운송 포인트 n개의 좌표를 담은 2차원 정수 배열 points와 로봇 x대의 운송 경로를 담은 2차원 정수 배열 routes가 매개변수로 주어집니다. 이때 모든 로봇이 운송을 마칠 때까지 발생하는 위험한 상황의 횟수를 return 하도록 solution 함수를 완성해 주세요.

---

포인트

1. 다차원 좌표 이동: 각 로봇은 (r, c) 형식의 2차원 좌표로 나타낼 수 있는 포인트들을 따라 이동합니다. 이 좌표들을 통해 로봇의 경로가 정의됩니다.

2. 동시 출발: 모든 로봇은 동시에 0초에 출발하며, 이동은 1초에 한 칸씩 수행됩니다. 이는 로봇들의 동선이 겹칠 수 있는 여지를 만듭니다.

3. 최단 경로 우선: 로봇은 다음 포인트로 이동할 때 최단 경로를 선택합니다. 최단 경로가 여러 개인 경우, r 좌표의 변화를 우선합니다.

4. 충돌 위험: 두 대 이상의 로봇이 동시에 같은 좌표에 도달할 경우 충돌 위험 상황으로 간주하며, 이러한 상황의 발생 횟수를 계산해야 합니다.

5. 성능 고려: 이 문제의 효율적 해결을 위해서는 각 로봇의 경로를 추적하고, 모든 시간대에 대해 모든 로봇의 위치를 파악하여 충돌 가능성을 검토하는 알고리즘이 필요합니다. 이는 특히 로봇 수(x)와 포인트 수(n)가 클 때 성능상의 고려가 필요합니다.

이 문제를 해결하기 위해서는 로봇의 이동 경로 관리와 충돌 검사 로직을 효율적으로 설계하는 것이 중요합니다.

---

내 답안

from collections import Counter

def robot_path(points, route):
    # 첫 번째 포인트를 기준으로 초기 위치 설정
    r, c = points[route[0]-1]
    path = [(r, c)]

    # 주어진 경로에 따라 이동 경로 계산
    for i in range(len(route)-1):
        # 현재 포인트
        r1, c1 = points[route[i]-1]
        # 다음 포인트
        r2, c2 = points[route[i+1]-1]

        # r과 c의 증가 또는 감소 방향 설정
        dr = 1 if r1 < r2 else -1
        dc = 1 if c1 < c2 else -1

        # r 좌표를 목표 포인트까지 이동
        while r2 != r1:
            r1 += dr
            path.append((r1, c1))
        # c 좌표를 목표 포인트까지 이동
        while c2 != c1:
            c1 += dc
            path.append((r1, c1))
    return path


def solution(points, routes):
    paths = []
    answer = 0

    # 각 경로에 대해 이동 경로를 계산하여 paths에 추가
    for route in routes:
        paths.append(robot_path(points, route))

    # 모든 경로 중 가장 긴 경로의 길이 계산
    max_length = max([len(path) for path in paths])

    # 각 시간별로 모든 로봇의 위치를 확인하고 충돌 감지
    for i in range(max_length):
        rows = []

        # 현재 시간에서 각 로봇의 위치를 rows에 추가
        for path in paths:
            if i < len(path):
                rows.append(path[i])
        # 위치별 로봇 수 계산
        row_counts = Counter(rows)
        # 두 대 이상의 로봇이 한 위치에 있는 경우, 충돌로 간주
        for count in row_counts.values():
            if count > 1:
                answer += 1
    return answer

---

결론 및 느낀점

이 문제를 통해 2차원 공간에서 로봇들의 동시적 이동을 모델링하고, 충돌 검출 알고리즘을 설계하는 복잡한 문제를 해결해 볼 수 있었습니다. 특히, 로봇이 이동하는 경로를 계산하고, 이 경로를 시간별로 분석하여 충돌이 발생하는 상황을 파악하는 과정은 로보틱스와 자동화 시스템에서 흔히 볼 수 있는 중요한 챌린지 중 하나입니다.

주요 학습 포인트:

1. 경로 계산의 정확성: 로봇의 이동 경로를 계산할 때, 각 지점 간의 최단 경로를 정확하게 계산하는 것이 중요했습니다. 이 과정에서 행과 열의 변화 우선순위를 설정하는 등, 문제의 요구사항에 맞게 경로를 세밀하게 조정해야 했습니다.

2. 충돌 감지 메커니즘: 각 시간 단위로 로봇의 위치를 파악하고, 같은 위치에 여러 로봇이 동시에 존재하는지 확인하는 로직을 구현하는 과정에서, collections.Counter를 활용하여 효율적으로 데이터를 처리하는 방법을 배웠습니다.

3. 알고리즘 효율성: 다수의 로봇과 경로를 관리하는 과정에서 성능 최적화의 중요성을 다시 한 번 깨달았습니다. 로봇 수가 많을수록, 그리고 이동 경로가 길수록 처리해야 할 데이터 양이 증가하기 때문에, 이를 효율적으로 관리하는 방법을 고민하는 것이 중요했습니다.

이러한 경험을 통해, 실제 작업 현장에서 발생할 수 있는 다양한 문제에 대해 보다 체계적이고 실용적인 해결 방안을 모색할 수 있는 능력을 키울 수 있었습니다. 또한, 실시간 데이터 처리와 이벤트 기반 프로그래밍에 대한 이해도를 높일 수 있는 좋은 기회였습니다.