[ 프로그래머스 ] [PCCP 기출문제] 3번 / 충돌위험 찾기 (Python)

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

프로그래머스

 

난이도 : Level 2 
알고리즘 유형 : 구현, 시뮬레이션 
풀이 시간 : 44분 

문제 풀이 

물류 센터에는 N개의 포인트가 존재한다. 또한, 로봇마다 정해진 운송 경로를 통해 시작 포인트부터 마지막 포인트까지 이동해야 한다. 로봇은 1초에 한 칸씩 움직일 수 있고, 모든 로봇이 동시에 움직인다. 움직이는 과정 중 로봇의 좌표가 중복되는 경우의 수를 구하자.

 

먼저, 로봇의 움직임 조건은 다음과 같다. 

 

1. 최단경로로 이동. 우선순위는 r이 변한 뒤, c가 변하는 순서로 주어진다.
2. 마지막 포인트에 도착한 로봇은 즉시 벗어난다.

 

여기서, 최단경로의 우선순위는 쉽게 말해, 상하좌우로 잡을 수 있다. 따라서 방향벡터를 [상, 하, 좌, 우] 순서로 잡아주었다. 이후, 최단거리를 구하는 경우에는 목적지까지의 거리가 작은 경우에만 업데이트 해주었다. 맵에 장애물이 존재하지 않기 때문에, 최단거리는 맨해튼거리를 통해 계산해주었다.

 

로봇은 여러 포인트를 경유해야 하는 경우도 존재한다. 이를 확인하기 위해 `routes`의 로봇 경로를 `deque`를 사용하여 묶어주었다. 이후, 도착 경로를 인덱스의 0번째 포인트로 확인하였고, 만약 경유해야 하는 지점에 도착하는 경우, deque의 메서드인 `popleft()`를 사용해 빠져나왔다.

 

로봇의 위험 상황을 판단하기 위해서는 `arrived_loc`과 `collision` 집합을 사용하였다. 먼저, 새로 업데이트 된 좌표가 `arrived_loc` 집합에 속해있는지를 판단해주었고, 만약 이미 현재 좌표에 이동한 이력이 있으면, 위험 상황 체크를 위해 `collision` 집합에 삽입해주었고, 아닌 경우에는 `arrived_loc`에 저장해주었다.

 

총 시간복잡도로는 $O(4 * 100 * 100)$이 소요된다. 이는 새로운 최단거리를 찾기 위한 반복문, 모든 로봇을 동시에 움직이기 위한 반복문, 총 이동하는 시간의 곱으로 표현할 수 있다.

 

코드

'''
1. 2차원 좌표의 n개의 포인트 존재, 서로다른 번호를 갖는다.
2. 로봇마다 정해진 운송 경로가 존재. m개이며, 할당된 포인트 순서대로 방문
3. 사용되는 로봇은 x대, 0초에 동시 출발
4. 최단경로로 이동. 우선순위는 r이 변한 뒤, c가 변하는 이동 순서
5. 마지막 포인트에 도착한 로봇은 벗어난다.

현재 설정대로 로봇이 움직일 때 위험 상황이 총 몇 번 일어나는지 알고싶음
- 어떤 시간에 여러 좌표에서 위험 상황이 발생한다면 그 횟수를 모두 더함

풀이 : 좌표의 위치 초기화
2차원 grid
최단경로 생각해주기 : however, 장애물은 없기 때문에 맨해튼거리로 계산 가능
현재 로봇의 위치를 생각해주기 : 어디로 가야할 지 정보를 찾기
'''
from collections import deque

dr = [-1, 1, 0, 0]
dc = [0, 0, 1, -1]

def solution(points, routes):
    answer = 0
    
    def get_distance(r1, c1, r2, c2):
        return abs(r1 - r2) + abs(c1 - c2)
    
    def move_robots(robots, routes):
        # 겹치는 위치 체크해야된다.
        new_robot_loc = []
        arrived_loc = set()
        collision = set()
        for robot in range(len(robots)):
            # 이미 종료한 로봇에 대한 처리
            if not robots[robot]:
                new_robot_loc.append(0)
                continue
            # 현재 위치에서 목적지까지 위치 먼저 계산
            r, c = robots[robot]
            dest = routes[robot][0]
            er, ec = points[dest]
            cur_dist = 10001
            # 새로운 위치 계산해보기
            new_r, new_c = r, c
            for d in range(len(dr)):
                nr, nc = r + dr[d], c + dc[d]
                if 0 <= nr < n and 0 <= nc < n:
                    new_dist = get_distance(nr, nc, er, ec)
                    if new_dist < cur_dist:
                        new_r, new_c = nr, nc
                        cur_dist = new_dist
            # 현재 위치 일단 중복되는지 저장
            if (new_r, new_c) in arrived_loc:
                collision.add((new_r, new_c))
            else:
                arrived_loc.add((new_r, new_c))
            # 현재 위치가 목적지인지 확인
            if grid[new_r][new_c] == dest:
                routes[robot].popleft()
            # 종료되었다면, 빠져나가기
            if not routes[robot]:
                new_robot_loc.append(0)
            else:
                # 새로운 로봇 위치를 저장
                new_robot_loc.append((new_r, new_c))
        return new_robot_loc, routes, len(collision)
    
    
    n = 100
    grid = [[0] * (n) for _ in range(n)]
    points = [0] + points
    for i in range(1, len(points)):
        grid[points[i][0] - 1][points[i][1] - 1] = i
        points[i] = (points[i][0] - 1, points[i][1] - 1)
    # 로봇 정보 찾기
    cur_robots = [0]
    # 시작 위치부터 겹치는 경우도 생각해줘야한다.
    arrived_loc = set()
    collision = set()
    for i in range(len(routes)):
        routes[i] = deque(routes[i])
        cur_robots.append(points[routes[i].popleft()])
        if cur_robots[-1] in arrived_loc:
                collision.add(cur_robots[-1])
        else:
            arrived_loc.add(cur_robots[-1])
    answer += len(collision)
    
    robot_cnt = len(routes) + 1
    routes = [0] + routes
    # 로봇 움직이기 시작
    while True:
        # 1. 로봇 동시에 움직이기
        cur_robots, routes, collision = move_robots(cur_robots, routes)
        answer += collision
        # 2. 종료조건 확인
        if cur_robots.count(0) == robot_cnt:
            break
            
    return answer

배운 점 

프로그래머스 페이지에서 디버깅을 진행하였더니, solution() 내부의 while 문 조건을 디버깅용으로 변경해두었다는 것을 잊어먹고 채점하기를 눌러 계속 틀리는 현상을 겪었다., 이를 방지하기 위해, 사이트에서 문제를 풀어나가는 경우에는 디버깅 위치를 잘 파악하거나 메모해두는 습관을 들여야 할 것 같다.