[PGM] #PCCP 기출문제 3번 충돌위험 찾기 (Python)[PGM] #PCCP previous exam 3rd Find collision risk (Python)
📅
🚀
알고리즘 분류 🔗
구현
🚀
문제 설명 🔗
- points 배열은 2차원 배열로, 출발, 혹은 도착 지점의 좌표를 나타냅니다.
- routes 배열은 2차원 배열로, 한 로봇의 이동 경로를 나타냅니다.
- 예를 들어, points = [[0, 0], [0, 1], [1, 1], [1, 0]]이고, routes = [[1, 2, 3, 4], [4, 3, 2, 1]]이라면, 첫 번째 로봇은 (0, 0)에서 출발하여 (0, 1), (1, 1)을 거쳐 (1, 0)에 도착합니다. 두 번째 로봇은 (1, 0)에서 출발하여 (1, 1), (0, 1)을 거쳐 (0, 0)에 도착합니다.
- 로봇들은 한 번에 한 칸씩 이동하며, 이동 경로는 상하좌우로만 가능합니다. 최적 경로로 이동하지만, 같은 최적 경로가 존재할 때 x축 방향으로 먼저 이동하는 경로를 선택합니다. 이동 경로에 다른 로봇이 있을 경우 충돌이 발생합니다.
🚀
풀이 🔗
- 먼저 로봇이 이동할 경로를 paths에 저장합니다. paths는 routes의 각 경로를 복사한 2차원 배열입니다.
- 다음과 같이 저장됩니다. [[[출발지점], [도착지점1], [도착지점2], ...], [[출발지점], [도착지점1], [도착지점2], ...], ...]
- grid라는 2차원 배열을 만들어 현재 각 좌표에 몇 대의 로봇이 있는지 저장합니다.
- paths의 각 경로를 이동시키며 충돌이 발생하는지 확인합니다.
- 충돌이 발생하면 answer에 1을 더합니다.
- 충돌이 발생하지 않으면 grid에 로봇이 있다는 표시를 합니다.
- 출발지점과 도착지점이 같아지면 해당 경로를 삭제합니다.
- 이때, 경로가 2개 이상 남아있을 경우 도착지점을 삭제합니다.
- 경로에 모두 도착했을 경우 출발지점을 [0, 0]으로 변경합니다.
- 모든 로봇이 이동을 마쳤을 때 answer를 반환합니다.
🚀
코드 - 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🚀
핵심 🔗
- 충돌이 발생하는지 확인하기 위해 탐색 시간을 줄이기 위해 grid를 사용합니다.
- 여러 로봇이 한 곳에서 충돌이 발생해도 한 번만 카운트합니다.
- 도착 지점이 여러 개인 경우, 도착 지점을 어떻게 관리 할 것인가가 중요합니다.