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

문제

충돌위험 찾기 (PCCP 기출문제 3번)

프로그래머스

 

아이디어

얼핏 문제를 읽다보면 bfs라고 생각하고 접근하기 쉬운 것 같다.

모든 point에 대해서 bfs를 사용해 최단 경로를 구해놓은 뒤, 로봇들의 이동 경로를 저장해 놓고 풀이했는데 시간초과에서 벗어나지 못했다.

 

문제에서 간과했던 부분이 있는데,

4번에서 r 좌표가 변하는 이동을 c 좌표가 변하는 이동보다 먼저 한다는 조건이다.

 

다시 해석하자면 현재 포인트 -> 다음 포인트로 갈 때 r 좌표가 같아질 때까지 이동한 후, c 좌표가 같아질 때까지 이동한다는 의미이다.

즉 아래와 같은 코드로 표현할 수 있다. (dx, dy 가중치나 visited 배열 등이 필요없다.)

while x != nx:
    x += 1 if nx > x else -1
    path.append((x, y))
while y != ny:
    y += 1 if ny > y else -1
    path.append((x, y))

 

이를 고려해서 다음과 같은 과정으로 문제를 해결했다.

 

1. 각 로봇들이 시작 지점 -> 도착 지점으로 가는 이동 경로에 있는 좌표 정보를 저장한다.

2. 매 초 마다 동일한 좌표를 가지는 로봇의 수를 카운트한다.

3. 동일 좌표인 로봇이 2개 이상이면 위험 상황으로 카운트한다.

 

전체 코드

from collections import defaultdict

def solution(points, routes):
    answer = 0
    n = len(routes)
        
    paths = []
    for i in range(n):
        cur = routes[i][0]
        x, y = points[cur-1]
        path = [(x, y)]
        for nxt in routes[i][1:]:
            nx, ny = points[nxt-1]
            while x != nx:
                x += 1 if nx > x else -1
                path.append((x, y))
            while y != ny:
                y += 1 if ny > y else -1
                path.append((x, y))
        paths.append(path)
    
    max_len = 0
    for path in paths:
        if len(path) > max_len:
            max_len = len(path)
    for path in paths:
        if len(path) < max_len:
            path += [(0, 0)]*(max_len-len(path))

    for j in range(max_len):
        lst = [paths[i][j] for i in range(n) if paths[i][j] != (0, 0)]
        cnt = defaultdict(int)
        for x, y in lst:
            cnt[(x, y)] += 1
        for k, v in cnt.items():
            if v >= 2:
                answer += 1
        
    return answer