[Programmers] Lv.2 _ [PCCP 기출문제] 3번 / 충돌 위험 찾기

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

 

풀이

운송 포인트 2차원 배열: points

운송 경로 2차원 배열: routes

 

흐름은

1. 각 운송 로봇 경로의 모든 칸을 배열에 담는다.

      1-1.  모든 운송 로봇을 한 배열에 담는다.

      1-2. 운송 포인트 별로 출발지 - 도착지를 갱신하며 모든 운송 포인트를 돈다.

2. 시점을 순회하며 같은 충돌 위험 좌표의 개수를 센다.

      2-1. 같은 좌표가 2개 이상이어야 한다.

 

운송 로봇의 경로는

1) 출발지 좌표 r  == 도착지 좌표 r 될 때까지 r 좌표 한 칸씩 전진

2) 출발지 좌표 c == 도착지 좌표 c 될 때까지 c 좌표 한 칸씩 전진

이 경로를 리스트에 담는다.

운송 포인트가 여러 개라면 출발지 - 도착지를 갱신하며 리스트에 경로를 추가한다.

 

충돌 위험 좌표의 개수를 세기 위해

3차원 배열을 순회하며, 해당 시점의 좌표들을 리스트에 담는다.

중복을 제거하고 각 좌표의 개수를 세고, 2개 이상일 경우에만 answer에 1을 더한다.

 

충돌 위험 좌표 개수 세는 로직 구현하는 데 시간이 조금 오래 걸렸다.

단순히 중복을 제거하는게 아니라 2개 이상인 좌표들을 세야했기 때문에, list를 set으로 만들고 set을 순회하며 list내의 개수를 셌다.

이 방법 말고도 더 간단한 방법이 있을 것 같지만 생각나는 방식대로 구현했다.

 

코드

def findRoutes(cur, des, pRoutes):
    cr = cur[0]
    cc = cur[1]
    dr = des[0]
    dc = des[1]

    if cr == dr and cc == dc:
        return pRoutes

    pRoutes.append(cur)

    if cr < dr:
        findRoutes([cr + 1, cc], des, pRoutes)
    elif cr > dr:
        findRoutes([cr - 1, cc], des, pRoutes)
    else:
        if cc < dc:
            findRoutes([cr, cc + 1], des, pRoutes)
        elif cc > dc:
            findRoutes([cr, cc - 1], des, pRoutes)

    return pRoutes


def solution(points, routes):
    answer = 0
    total = []

    for i in range(len(routes)):
        pRoutes = []
        for j in range(len(routes[i])):
            if j != len(routes[i]) - 1:
                cur = points[routes[i][j] - 1]
                des = points[routes[i][j + 1] - 1]
                pRoutes = findRoutes(cur, des, pRoutes)
            else:
                pRoutes.append(points[routes[i][j] - 1])
        total.append(pRoutes)

    for k in range(max(len(sub_total) for sub_total in total)):
        one = []
        for m in range(len(routes)):
            if k <= len(total[m]) - 1:
                o = total[m][k]
                one.append((o[0], o[1]))
        n = len(one)
        for sub_one in list(set(one)):
            if one.count(sub_one) > 1:
                answer += 1

    return answer