[PGM] PCCP Past Exam Question 3: Finding Collision Risks (Python)

https://school.programmers.co.kr/learn/courses/30/lessons/340211↗

• points is a two-dimensional array containing the coordinates of
  starting points or destinations
  .
• routes is a two-dimensional array describing
  each robot's route
  .
• For example, if points = [[0, 0], [0, 1], [1, 1], [1, 0]] and routes = [[1, 2, 3, 4], [4, 3, 2, 1]], the first robot starts at (0, 0), passes through (0, 1) and (1, 1), and finishes at (1, 0). The second robot starts at (1, 0), passes through (1, 1) and (0, 1), and finishes at (0, 0).
• Robots move one cell at a time, only up, down, left, or right. They follow an optimal route, preferring movement along the x-axis when several optimal routes exist. A
  collision occurs if another robot occupies a position on the route
  .

1. First, store the robots' routes in
   paths
   , a two-dimensional array copied from routes.
   • The structure is [[[starting point], [destination 1], [destination 2], ...], [[starting point], [destination 1], [destination 2], ...], ...].
2. Create a two-dimensional array called
   grid
   to track how many robots currently occupy each coordinate.
3. Advance each route in paths and check for collisions.
   • If a collision occurs, add 1 to answer.
   • Otherwise, mark the robot's presence in grid.
   • When a starting point and destination become equal, remove that route segment.
     • If at least two destinations remain, remove the destination just reached.
     • If the robot has reached every destination on its route, change its starting point to [0, 0].
4. Return answer once all robots have finished moving.

def solution(points, routes):
	answer = 0
	paths = [[points[j - 1][:] for j in route] for route in routes]
	
	grid = [[0] * 101 for _ in range(101)]
	
	for path in paths: # 출발 지점에서의 충돌 확인
		x, y = path[0]
		if grid[x][y] == 1:
			grid[x][y] += 1
			answer += 1
		elif grid[x][y] == 0:
			grid[x][y] = 1
	
	while True:
		active_paths = len(paths) # 활성화된 경로의 수 (0이면 종료)
		grid = [[0] * 101 for _ in range(101)] # 그리드 초기화
		
		for path in paths: 
			if path[0] == [0, 0]: # 최종 도착지에 도착한 로봇
				active_paths -= 1
				continue
		
			x1, y1 = path[0] 
			x2, y2 = path[1]
			
			if x1 < x2: # 경로 이동 (x축 우선)
				path[0][0] += 1
			elif x1 > x2:
				path[0][0] -= 1
			elif y1 < y2:
				path[0][1] += 1
			elif y1 > y2:
				path[0][1] -= 1
			
			x, y = path[0] # 충돌 확인
			if grid[x][y] == 1:
				grid[x][y] += 1
				answer += 1
			elif grid[x][y] == 0:
				grid[x][y] = 1
			
			if path[0] == path[1]: # 도착지에 도착한 경우
				if len(path) > 2:	# 추가 경로가 있는 경우
					del path[1]
				else:	 # 모든 경로를 이동한 경우
					path[0] = [0, 0]
					active_paths -= 1
		
		if active_paths == 0:
			break
	
	return answer

• Use grid to reduce the search time needed to detect collisions.
• Count a collision at a location only once, even if several robots collide there.
• When there are multiple destinations, how you manage them is important.