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

혼자 꽈배기처럼 꼬아서 생각해서 시간 초과가 났던 문제였다..

 

프로그래머스

 

문제

 

어떤 물류 센터는 로봇을 이용한 자동 운송 시스템을 운영합니다. 운송 시스템이 작동하는 규칙은 다음과 같습니다.

1. 물류 센터에는 (r, c)와 같이 2차원 좌표로 나타낼 수 있는 n개의 포인트가 존재합니다. 각 포인트는 1~n까지의 서로 다른 번호를 가집니다.
2. 로봇마다 정해진 운송 경로가 존재합니다. 운송 경로는 m개의 포인트로 구성되고 로봇은 첫 포인트에서 시작해 할당된 포인트를 순서대로 방문합니다.
3. 운송 시스템에 사용되는 로봇은 x대이고, 모든 로봇은 0초에 동시에 출발합니다. 로봇은 1초마다 r 좌표와 c 좌표 중 하나가 1만큼 감소하거나 증가한 좌표로 이동할 수 있습니다.
4. 다음 포인트로 이동할 때는 항상 최단 경로로 이동하며 최단 경로가 여러 가지일 경우, r 좌표가 변하는 이동을 c 좌표가 변하는 이동보다 먼저 합니다.
5. 마지막 포인트에 도착한 로봇은 운송을 마치고 물류 센터를 벗어납니다. 로봇이 물류 센터를 벗어나는 경로는 고려하지 않습니다.

이동 중 같은 좌표에 로봇이 2대 이상 모인다면 충돌할 가능성이 있는 위험 상황으로 판단합니다. 관리자인 당신은 현재 설정대로 로봇이 움직일 때 위험한 상황이 총 몇 번 일어나는지 알고 싶습니다. 만약 어떤 시간에 여러 좌표에서 위험 상황이 발생한다면 그 횟수를 모두 더합니다.

운송 포인트 n개의 좌표를 담은 2차원 정수 배열 points와 로봇 x대의 운송 경로를 담은 2차원 정수 배열 routes가 매개변수로 주어집니다. 이때 모든 로봇이 운송을 마칠 때까지 발생하는 위험한 상황의 횟수를 return 하도록 solution 함수를 완성해 주세요.

 

풀이

 

프로그래머스는 문제가 길어도 설명이 아주아주 친절하다. 입출력 예 설명을 보면 이해가 쏙 된다.
문제에서 중요한 포인트는 하이라이트 친 부분!
항상 최단 경로로 이동하며 최단 경로가 여러 가지일 경우, r 좌표가 변하는 이동을 c 좌표가 변하는 이동보다 먼저 하는 것이다.

처음에는 몇번째에 어느 좌표로 갔는지 이차원 리스트를 생성해서 풀었다.
입출력 예 1번을 리스트로 나타내면 아래 표 처럼 나오길 바랬다.

0	1	2	3	4	5	6	7...
(1,4)	(2,4)	(3,4)	(4,4)	(5,4)	(6,4)
(3,2)	(4,2)	(4,3)	(4,4)	(4,5)	(4,6)	(4,7)
(6,4)	(5,4)	(4,4)	(3,4)	(2,4)	(1,4)

 

한 좌표에 4대의 로봇이 들어와도 충돌 카운트는 +1이 되므로 check 리스트를 또 만들었다.
이 방법은 내가 보기 좋게 만든거였지 파이썬은 계속 리스트를 뒤적거려야해서 힘들었나보다.

 

 

테스트케이스 9, 13, 19번은 시간 초과, 18번 런타임 에러는 이차원 리스트를 생성할때 크기가 문제였던 것 같다.

사실 방문 체크 리스트 하나만 있으면 됐는데 너무 어렵게 생각했나보다.
예를 들어 입출력 예 1번을 보면 첫번째 routes[4,2]는 points[1,4]에서 points[6,4]으로 이동하므로
(0,1,4), (1,2,4), (2,3,4), (3,4,4), (4,5,4), (5,6,4) 이렇게 맨 앞은 인덱스 값, 그 다음은 x,y 좌표를 1차원 리스트에 넣어주고 Counter 모듈을 사용해서 중복 갯수를 카운트했다.
딕셔너리로 변경하면 key 값이 (인덱스,x좌표,y좌표)가 되고 value 는 중복 갯수이므로 dict(count).values() 값이 1을 초과하는 것만 뽑아서 길이를 리턴했다.

 

정답 코드

from collections import Counter

def solution(points, routes):
    visited = []		# 방문 기록 (몇번째,x좌표,y좌표)
    for route in routes:
        q = []
        for i in route:
            x, y = points[i-1]
            q.append((x,y))

        cx, cy = q.pop(0)	# 현재 위치
        visited.append((0,cx,cy))
        cnt = 1
        while q:
            nx, ny = q.pop(0)	# 다음 위치
            while cx != nx:
                if cx < nx:
                    cx += 1
                else:
                    cx -= 1
                visited.append((cnt,cx,cy))
                cnt += 1
            while cy != ny:
                if cy < ny:
                    cy += 1
                else:
                    cy -= 1
                visited.append((cnt,cx,cy))
                cnt += 1
                
    count = Counter(visited)			# Counter 모듈을 사용해서 중복 갯수 찾기
    answer = [i for i in dict(count).values() if i > 1]		# 중복값이 1을 초과하면 저장
    return len(answer)

 

시간복잡도가 첫번째 제출한 것과 아주 다르다.

 

그리고 문제를 제출하고 다른 고수님들 코드를 보니 파이썬다운 코드가 많았다.

while cx != nx:
    dx = 1 if cx < nx else -1
    cx += dx
    visited.append((cnt,cx,cy))