[PGM] PCCP真题第3题：查找碰撞风险（Python）

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