[PCCP 기출문제] 3번 / 충돌위험 찾기

문제 설명

물류 센터에는 n개의 포인트가 존재하며, 각 포인트는 (r, c) 형태의 2차원 좌표를 가집니다.

여러 대의 로봇은 각각 정해진 운송 경로를 따라 이동합니다.

각 로봇의 경로에는 방문해야 하는 포인트 번호가 순서대로 주어지며, 로봇은 첫 번째 포인트에서 시작하여 나머지 포인트를 차례대로 방문합니다.

모든 로봇은 0초에 동시에 출발합니다.

로봇은 1초마다 다음과 같이 한 칸 이동할 수 있습니다.

• r 좌표를 1 증가 또는 감소
• c 좌표를 1 증가 또는 감소

로봇은 항상 다음 포인트까지 최단 경로로 이동합니다.

최단 경로가 여러 개 존재하는 경우에는

r 좌표를 먼저 이동한 뒤 c 좌표를 이동합니다.

마지막 포인트에 도착한 로봇은 운송을 종료하고 물류 센터를 벗어납니다.

같은 시간에 같은 좌표에 2대 이상의 로봇이 존재한다면 위험 상황이 1번 발생한 것으로 판단합니다.

같은 시간에 여러 좌표에서 위험 상황이 발생한다면 각각을 모두 계산해야 합니다.

모든 로봇의 운송이 끝날 때까지 발생하는 위험 상황의 총횟수를 구해야 합니다.

---

제한사항

• 2 ≤ n ≤ 100
• 각 포인트의 좌표는 (r, c) 형태로 주어집니다.
• 1 ≤ r, c ≤ 100
• 서로 다른 포인트가 같은 좌표를 가지는 경우는 없습니다.
• 로봇의 수는 최대 100대입니다.
• 각 로봇은 최대 100개의 포인트를 방문합니다.
• 모든 로봇의 운송 경로 길이는 같습니다.
• 같은 포인트를 연속으로 방문하는 경우는 없습니다.

입출력 예

pointsroutesresult

[[3, 2], [6, 4], [4, 7], [1, 4]]	[[4, 2], [1, 3], [2, 4]]	1
[[3, 2], [6, 4], [4, 7], [1, 4]]	[[4, 2], [1, 3], [4, 2], [4, 3]]	9
[[2, 2], [2, 3], [2, 7], [6, 6], [5, 2]]	[[2, 3, 4, 5], [1, 3, 4, 5]]	0

---

문제 풀이

이 문제는 모든 로봇이 움직이는 과정을 직접 확인하는 시뮬레이션 문제입니다.

핵심은 각 로봇이

몇 초에 어떤 좌표에 있는지

를 구한 뒤, 같은 시간과 같은 좌표에 존재하는 로봇의 수를 세는 것입니다.

로봇의 이동 방법이 완전히 정해져 있기 때문에 각 로봇의 전체 이동 경로를 미리 구할 수 있습니다.

---

1. 포인트 번호를 실제 좌표로 변환하기

routes에는 좌표가 직접 들어 있는 것이 아니라 방문해야 하는 포인트 번호가 들어 있습니다.

예를 들어

points[0] = [3, 2]

라면 1번 포인트의 좌표는

(3, 2)

입니다.

따라서 로봇의 경로가

[4, 2]

라면 실제로는

4번 포인트의 좌표 → 2번 포인트의 좌표

순서대로 이동하게 됩니다.

각 로봇마다 방문할 포인트 번호를 실제 (r, c) 좌표로 변환하면서 이동 경로를 만들면 됩니다.

---

2. 로봇은 항상 r 좌표를 먼저 이동한다

현재 위치가

(r1, c1)

이고 다음 목적지가

(r2, c2)

라고 하겠습니다.

두 좌표 사이의 최단 거리는

|r1 - r2| + |c1 - c2|

입니다.

하지만 최단 경로는 여러 개 존재할 수 있습니다.

문제에서는 이동 방법까지 정해주었습니다.

최단 경로가 여러 개라면 r 좌표가 변하는 이동을 먼저 한다.

따라서 로봇은 먼저 r1을 r2와 같게 만든 뒤, c1을 c2와 같게 만들면 됩니다.

예를 들어

(1, 2) → (3, 4)

로 이동한다고 하겠습니다.

먼저 r 좌표를 이동하면

(1, 2) → (2, 2) → (3, 2)

가 됩니다.

그다음 c 좌표를 이동하면

(3, 2) → (3, 3) → (3, 4)

가 됩니다.

따라서 전체 이동 경로는

(1, 2) → (2, 2) → (3, 2) → (3, 3) → (3, 4)

로 하나로 결정됩니다.

---

3. 각 시간의 로봇 위치 기록하기

모든 로봇은 0초에 첫 번째 포인트에서 시작합니다.

따라서 출발 위치 역시 위험 상황을 판단할 때 포함해야 합니다.

예를 들어 어떤 로봇의 이동 경로가

(1, 2) → (2, 2) → (3, 2) → (3, 3)

이라면 시간에 따른 위치는 다음과 같습니다.

시간위치

0초	(1, 2)
1초	(2, 2)
2초	(3, 2)
3초	(3, 3)

따라서 각 로봇을 이동시키면서

시간 → 위치

정보를 기록할 수 있습니다.

모든 로봇에 대해 이 과정을 반복하면 특정 시간에 어떤 로봇들이 어느 좌표에 있었는지 확인할 수 있습니다.

---

4. 중간 포인트에 도착해도 다음 이동은 바로 이어진다

하나의 로봇은 여러 개의 포인트를 순서대로 방문합니다.

예를 들어 경로가

1번 → 3번 → 4번

이라고 하겠습니다.

로봇이 3번 포인트에 도착했다고 해서 한 번 더 정지하는 것은 아닙니다.

3번 포인트에 도착한 시간이 5초라면

• 5초에는 3번 포인트에 존재하고
• 6초에는 4번 포인트를 향해 한 칸 이동합니다.

따라서 각 구간을 연결할 때 중간 포인트의 위치를 중복해서 기록하지 않는 것이 중요합니다.

---

5. 같은 시간과 같은 좌표의 로봇 수를 센다

이제 모든 로봇의 위치를 시간별로 확인합니다.

특정 시간에 특정 좌표에 몇 대의 로봇이 존재하는지를 저장합니다.

예를 들어 5초의 로봇 위치가 다음과 같다고 하겠습니다.

로봇위치

1번	(3, 4)
2번	(3, 4)
3번	(2, 7)
4번	(5, 2)

(3, 4)에 로봇이 2대 존재하므로 위험 상황이 발생합니다.

따라서 이 시간에는 위험 상황을 1 증가시킵니다.

---

6. 로봇이 3대 이상 모여도 위험 상황은 1번이다

이 문제에서 특히 주의해야 할 부분입니다.

같은 시간, 같은 좌표에 로봇이 3대 있다고 하더라도 위험 상황을 로봇의 쌍 개수만큼 계산하는 것이 아닙니다.

예를 들어 한 좌표에 로봇이 3대 있다면

3C2 = 3

개의 충돌 가능성이 있다고 계산하는 것이 아니라,

해당 좌표에서 위험 상황이 발생했다는 사실 자체를 1번 계산합니다.

즉,

같은 좌표의 로봇 수위험 상황 횟수

1대	0
2대	1
3대	1
4대	1

입니다.

따라서 각 시간과 좌표에 대해 로봇의 수가 2 이상인지만 확인하면 됩니다.

---

7. 같은 시간에 여러 좌표에서 충돌하면 각각 계산한다

반대로 같은 시간에 서로 다른 여러 좌표에서 위험 상황이 발생할 수 있습니다.

예를 들어 10초에

• (2, 3)에 로봇 2대
• (5, 7)에 로봇 3대

가 있다고 하겠습니다.

두 좌표 모두 위험 상황이므로 해당 시간의 위험 상황은 총

2번

입니다.

즉, 위험 상황은

시간 + 좌표

를 하나의 기준으로 생각해야 합니다.

---

8. 마지막 포인트에 도착한 순간까지는 포함한다

로봇은 마지막 포인트에 도착하면 물류 센터를 벗어납니다.

따라서 마지막 포인트에 도착한 그 순간의 위치는 위험 상황 판단에 포함됩니다.

예를 들어 로봇이 7초에 마지막 포인트에 도착했다면

7초에는 해당 좌표에 존재합니다.

따라서 다른 로봇이 같은 7초에 같은 좌표에 있다면 위험 상황이 발생합니다.

하지만 8초부터는 물류 센터를 벗어났으므로 더 이상 위치를 확인하지 않습니다.

---

전체 흐름

문제를 해결하는 과정은 다음과 같습니다.

1. 각 로봇의 첫 번째 포인트 좌표를 0초 위치로 기록합니다.
2. 현재 포인트에서 다음 포인트로 이동합니다.
3. r 좌표가 다르다면 r 좌표부터 목적지와 같아질 때까지 이동합니다.
4. 이후 c 좌표가 같아질 때까지 이동합니다.
5. 한 칸 이동할 때마다 시간을 1 증가시키고 현재 위치를 기록합니다.
6. 모든 로봇의 전체 이동 경로에 대해 같은 시간과 같은 좌표에 몇 대의 로봇이 존재하는지 계산합니다.
7. 로봇이 2대 이상 존재하는 (시간, 좌표)마다 위험 상황을 1씩 증가시킵니다.
8. 모든 위험 상황의 수를 더해 반환합니다.

---

핵심 정리

이 문제는 로봇의 이동 경로가 정해져 있기 때문에 각 로봇의 위치를 시간 순서대로 시뮬레이션하는 것이 핵심입니다.

특히 다음 조건들을 정확하게 처리해야 합니다.

• 모든 로봇은 0초의 시작 위치부터 위험 상황 판단에 포함됩니다.
• 최단 경로 중 반드시 r 좌표를 먼저 이동합니다.
• 중간 포인트에서는 별도로 대기하지 않습니다.
• 같은 시간, 같은 좌표에 로봇이 2대 이상이면 위험 상황은 1번입니다.
• 로봇이 3대 이상 있어도 위험 상황을 여러 번 세지 않습니다.
• 같은 시간이라도 서로 다른 좌표에서 발생한 위험 상황은 각각 계산합니다.
• 마지막 포인트에 도착한 순간까지는 위험 상황 판단에 포함됩니다.

결국 모든 로봇에 대해

시간 + 좌표

를 기록한 뒤, 동일한 값이 2번 이상 등장하는 경우를 세면 문제를 해결할 수 있습니다.

---

시간 복잡도

각 포인트의 좌표는 1 ~ 100 범위이므로 두 포인트 사이의 최대 맨해튼 거리는

99 + 99 = 198

입니다.

각 로봇이 방문하는 포인트의 개수를 M, 로봇의 수를 X라고 하면 한 로봇이 이동하는 최대 거리는 대략

O(M × 198)

입니다.

모든 로봇의 이동 경로를 확인하므로 전체 시간 복잡도는

O(X × M × D)

로 볼 수 있습니다.

여기서 D는 두 포인트 사이의 최대 이동 거리이며 최대 198입니다.

문제에서

• 로봇의 수 X ≤ 100
• 경로 길이 M ≤ 100
• 한 구간의 이동 거리 D ≤ 198

이므로 모든 로봇의 이동을 직접 시뮬레이션해도 충분히 해결할 수 있습니다.

from collections import Counter

def solution(points, routes):
    answer = 0
    
    robot_path = []
    for route in routes:
        nr, nc = points[route[0]-1]
        path = [(nr, nc)]
        
        for point_num in route[1:]:
            r, c = points[point_num-1]
            while nr != r:
                if nr < r:
                    nr += 1
                else:
                    nr -= 1
                path.append((nr, nc))
            while nc != c:
                if nc < c:
                    nc += 1
                else:
                    nc -= 1
                path.append((nr, nc))
        robot_path.append(path)  
    
    max_time = max(len(path) for path in robot_path)
    
    for time in range(max_time):
        position = []
        
        for path in robot_path:
            if time < len(path):
                position.append(path[time])
        
        counter = Counter(position)
        
        for point, count in counter.items():
            if count >= 2:
                answer += 1
    
    return answer