문제 요약
물류센터에는 번호가 붙은 여러 포인트가 존재한다.
각 로봇은 정해진 포인트들을 순서대로 방문한다.
모든 로봇은 0초에 동시에 출발하며, 1초마다 상하좌우 중 한 방향으로 한 칸 이동한다.
다음 포인트까지는 항상 최단 경로로 이동한다.
최단 경로가 여러 개라면 다음 우선순위를 따른다.
r 좌표 이동 -> c 좌표 이동같은 시간에 같은 좌표에 로봇이 2대 이상 있다면 해당 좌표에서 위험 상황이 한 번 발생한다.
한 시간에 여러 좌표에서 충돌 위험이 발생하면 각 좌표를 모두 세어야 한다.
모든 로봇이 운송을 끝낼 때까지 발생하는 위험 상황의 총횟수를 구해야 한다.
핵심 아이디어
모든 로봇은 동시에 1초에 한 칸씩 움직인다.
따라서 시간을 1초씩 증가시키면서 다음 과정을 반복하면 된다.
- 현재 활동 중인 로봇들의 좌표를 센다.
- 같은 좌표에 로봇이 2대 이상 있다면 위험 상황을 더한다.
- 각 로봇을 다음 포인트 방향으로 한 칸 이동시킨다.
- 마지막 포인트에 도착한 로봇은 다음 시간부터 제거한다.
이 문제에서 중요한 점은 로봇 쌍의 개수가 아니라 위험한 좌표의 개수를 세는 것이다.
예를 들어 같은 좌표에 로봇 3대가 모여 있어도 위험 상황은 한 번이다.
로봇 3대가 좌표 (2, 3)에 존재
-> 위험 상황 1회r 좌표 우선 이동
현재 로봇 위치가 (r, c)이고 다음 목표가 (target_r, target_c)라고 하자.
먼저 r 좌표가 목표와 같은지 확인한다.
if r != target_r:r 좌표가 다르다면 목표 방향으로 1만큼 이동한다.
r += 1 if r < target_r else -1r 좌표가 이미 같다면 c 좌표를 이동한다.
else:
c += 1 if c < target_c else -1이렇게 구현하면 문제에서 주어진 이동 우선순위를 그대로 만족한다.
로봇 상태 관리
각 로봇마다 다음 정보를 저장한다.
현재 위치
positions[i]i번 로봇의 현재 [r, c] 좌표다.
다음 방문 포인트 인덱스
next_index[i]현재 로봇이 다음으로 방문해야 하는 경로상의 위치를 나타낸다.
로봇은 첫 번째 포인트에서 시작하므로 초기값은 1이다.
next_index = [1] * robot_count활동 여부
active[i]로봇이 아직 물류센터 안에서 운송 중인지 나타낸다.
마지막 포인트에 도착한 로봇은 해당 시간의 위험 상황을 확인한 뒤 물류센터에서 제거된다.
위험 상황 계산
현재 시간에 활동 중인 로봇들의 좌표를 Counter로 센다.
position_count = Counter(
tuple(positions[i])
for i in range(robot_count)
if active[i]
)좌표별 로봇 수가 2 이상인 좌표의 개수를 더한다.
answer += sum(
count >= 2
for count in position_count.values()
)파이썬에서 True는 숫자 1, False는 숫자 0으로 계산되므로 위 코드로 위험 좌표의 개수를 구할 수 있다.
마지막 포인트 도착 처리
로봇이 마지막 포인트에 도착한 시간에도 해당 좌표에 존재한다.
따라서 먼저 현재 시간의 위험 상황을 계산해야 한다.
그 후 다음 이동 단계에서 더 이상 방문할 포인트가 없다면 로봇을 비활성화한다.
if next_index[i] == len(routes[i]):
active[i] = False
continue이렇게 하면 마지막 포인트에 도착한 순간의 충돌은 포함하면서, 다음 시간부터는 해당 로봇을 계산에서 제외할 수 있다.
전체 코드
from collections import Counter
def solution(points, routes):
robot_count = len(routes)
# 모든 로봇은 경로의 첫 번째 포인트에서 시작한다.
positions = [
points[route[0] - 1][:]
for route in routes
]
# 다음으로 방문할 포인트는 경로의 두 번째 원소다.
next_index = [1] * robot_count
active = [True] * robot_count
answer = 0
while any(active):
# 현재 시간에 같은 좌표에 있는 로봇 수를 센다.
position_count = Counter(
tuple(positions[i])
for i in range(robot_count)
if active[i]
)
# 로봇이 2대 이상 있는 좌표마다 위험 상황 1회를 더한다.
answer += sum(
count >= 2
for count in position_count.values()
)
# 모든 로봇을 동시에 한 칸씩 이동시킨다.
for i in range(robot_count):
if not active[i]:
continue
# 마지막 포인트에 도착한 로봇은 다음 시간부터 제외한다.
if next_index[i] == len(routes[i]):
active[i] = False
continue
target_point = routes[i][next_index[i]] - 1
target_r, target_c = points[target_point]
r, c = positions[i]
# r 좌표를 먼저 이동한다.
if r != target_r:
r += 1 if r < target_r else -1
else:
c += 1 if c < target_c else -1
positions[i] = [r, c]
# 목표 포인트에 도착했다면 다음 포인트를 목표로 설정한다.
if r == target_r and c == target_c:
next_index[i] += 1
return answer동작 순서
각 반복문은 현재 시간의 상태를 나타낸다.
현재 위치 충돌 확인
-> 마지막 포인트 도착 로봇 제거
-> 나머지 로봇 한 칸 이동
-> 다음 시간0초의 시작 위치도 충돌 위험에 포함되어야 하므로 이동 전에 좌표를 세는 것이 중요하다.
모든 로봇의 위치를 시간별로 확인했을 때 같은 시간, 같은 좌표에 로봇이 2대 이상 모이는 위험 상황이 총 한 번 발생한다.
전체 경로를 미리 만들지 않은 이유
각 로봇의 전체 이동 경로를 리스트로 미리 만들 수도 있다.
하지만 포인트 사이의 거리는 최대 다음과 같다.
|r1 - r2| + |c1 - c2| <= 198로봇 하나가 최대 100개의 포인트를 방문하고, 로봇도 최대 100대이므로 모든 좌표를 튜플로 저장하면 메모리 사용량이 커질 수 있다.
현재 풀이에서는 각 로봇의 다음 정보만 저장한다.
- 현재 좌표
- 다음 포인트 인덱스
- 활동 여부
따라서 전체 경로를 저장하지 않고도 같은 시뮬레이션을 수행할 수 있다.
시간 복잡도
로봇 수를 x, 모든 로봇 중 가장 긴 이동 시간을 T라고 하자.
매 시간마다 모든 로봇의 위치를 확인하고 이동시킨다.
O(T × x)좌표 범위는 1~100이고, 경로에는 최대 100개의 포인트가 존재하므로 충분히 처리할 수 있다.
보다 정확히 표현하면 모든 시간 동안 로봇 상태를 확인하는 비용은 다음과 같다.
O(T × 로봇 수)공간 복잡도
각 로봇의 현재 상태와 현재 시간의 좌표별 개수를 저장한다.
O(로봇 수)전체 이동 경로를 미리 저장하지 않으므로 메모리를 적게 사용한다.
정리
이 문제는 모든 로봇을 동일한 시간축에서 움직이는 시뮬레이션 문제다.
핵심 포인트는 다음과 같다.
- 0초의 시작 위치부터 충돌 여부를 확인한다.
- 같은 좌표에 로봇이 몇 쌍 있는지가 아니라 위험한 좌표의 개수를 센다.
- 같은 좌표에 로봇이 3대 이상 있어도 위험 상황은 한 번이다.
- 이동할 때는 항상
r좌표를 먼저 변경한다. - 마지막 포인트에 도착한 시간의 충돌은 포함한다.
- 마지막 포인트에 도착한 로봇은 다음 시간부터 제외한다.
시간마다 좌표를 세고 모든 로봇을 한 칸 이동시키면 문제의 규칙을 그대로 구현할 수 있다.
