Research - [Coding Test]충돌 위험 찾기

- 링크

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

- 문제

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

물류 센터에는 (r, c)와 같이 2차원 좌표로 나타낼 수 있는 n개의 포인트가 존재합니다. 각 포인트는 1~n까지의 서로 다른 번호를 가집니다.

로봇마다 정해진 운송 경로가 존재합니다. 운송 경로는 m개의 포인트로 구성되고 로봇은 첫 포인트에서 시작해 할당된 포인트를 순서대로 방문합니다.

운송 시스템에 사용되는 로봇은 x대이고, 모든 로봇은 0초에 동시에 출발합니다. 로봇은 1초마다 r 좌표와 c 좌표 중 하나가 1만큼 감소하거나 증가한 좌표로 이동할 수 있습니다.

다음 포인트로 이동할 때는 항상 최단 경로로 이동하며 최단 경로가 여러 가지일 경우, r 좌표가 변하는 이동을 c 좌표가 변하는 이동보다 먼저 합니다.

마지막 포인트에 도착한 로봇은 운송을 마치고 물류 센터를 벗어납니다. 로봇이 물류 센터를 벗어나는 경로는 고려하지 않습니다.

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

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

제한사항

2 ≤ points의 길이 = n ≤ 100

points[i]는 i + 1번 포인트의 [r 좌표, c 좌표]를 나타내는 길이가 2인 정수 배열입니다.

1 ≤ r ≤ 100

1 ≤ c ≤ 100

같은 좌표에 여러 포인트가 존재하는 입력은 주어지지 않습니다.

2 ≤ routes의 길이 = 로봇의 수 = x ≤ 100

2 ≤ routes[i]의 길이 = m ≤ 100

routes[i]는 i + 1번째 로봇의 운송경로를 나타냅니다. routes[i]의 길이는 모두 같습니다.

routes[i][j]는 i + 1번째 로봇이 j + 1번째로 방문하는 포인트 번호를 나타냅니다.

같은 포인트를 연속으로 방문하는 입력은 주어지지 않습니다.

1 ≤ routes[i][j] ≤ n

- 답

def solution(points, routes):
    def move_point(start, end, points, newpoints, move, step = 0,a = 1):
        x1, y1 = points[start - 1]
        x2, y2 = points[end - 1]

        if a == 1:
            move.append([step,x1,y1])

        while x1 != x2 or y1 != y2 :
            step += 1
            if x1 < x2:
                x1 += 1
            elif x1 > x2:
                x1 -= 1
            elif y1 < y2:
                y1 += 1
            elif y1 > y2:
                y1 -= 1
            move.append([step,x1, y1])

        newpoints[start - 1] = [x1, y1]

    newpoints = [point[:] for point in points]
    move = []
    for i,route in enumerate(routes):
        if len(route) == 2 :
            move_point(route[0], route[1], points, newpoints, move)
        elif len(route) > 2 :
            step = 0
            a = 1
            for j in range(len(route)-1):
                move_point(route[j], route[j+1], points, newpoints, move, step, a)
                step = move[-1][0]
                a = 0

    duplicates_count = {}
    for m in move:
        tuple_key = tuple(m)
        if tuple_key in duplicates_count:
            duplicates_count[tuple_key] += 1
        else:
            duplicates_count[tuple_key] = 1

    answer = len([count for count in duplicates_count.values() if count not in [1]])
    return answer

solution([[3, 2], [6, 4], [4, 7], [1, 4]],[[4, 2], [1, 3], [2, 4]])
# 1

solution([[3, 2], [6, 4], [4, 7], [1, 4]],[[4, 2], [1, 3], [4, 2], [4, 3]])
# 9

solution([[2, 2], [2, 3], [2, 7], [6, 6], [5, 2]],[[2, 3, 4, 5], [1, 3, 4, 5]])
# 0

- 한 줄씩

1번 예제

points = [[3, 2], [6, 4], [4, 7], [1, 4]]
routes = [[4, 2], [1, 3], [2, 4]]

def move_point(start, end, points, newpoints, move, step = 0,a = 1):
    x1, y1 = points[start - 1]
    x2, y2 = points[end - 1]
    
    if a == 1:
        move.append([step,x1,y1])
    # 1초마다 r 좌표와 c 좌표 중 하나가 1만큼 감소하거나 증가한 좌표로 이동할 수 있습니다.
    # step = 초
    # r좌표 = x
    # c좌표 = y
    while x1 != x2 or y1 != y2 :
        step += 1
        # 다음 포인트로 이동할 때는 항상 최단 경로로 이동하며 최단 경로가 여러 가지일 경우, r 좌표가 변하는 이동을 c 좌표가 변하는 이동보다 먼저 합니다.
        if x1 < x2:
            x1 += 1
        elif x1 > x2:
            x1 -= 1
        elif y1 < y2:
            y1 += 1
        elif y1 > y2:
            y1 -= 1
        move.append([step,x1, y1])

    newpoints[start - 1] = [x1, y1]

newpoints = [point[:] for point in points]
move = []
for i,route in enumerate(routes):
    if len(route) == 2 :
        move_point(route[0], route[1], points, newpoints, move)
    elif len(route) > 2 :
        step = 0
        a = 1
        for j in range(len(route)-1):
            move_point(route[j], route[j+1], points, newpoints, move, step, a)
            step = move[-1][0]
            a = 0

move

[[0, 1, 4],
 [1, 2, 4],
 [2, 3, 4],
 [3, 4, 4],
 [4, 5, 4],
 [5, 6, 4],
 [0, 3, 2],
 [1, 4, 2],
 [2, 4, 3],
 [3, 4, 4],
 [4, 4, 5],
 [5, 4, 6],
 [6, 4, 7],
 [0, 6, 4],
 [1, 5, 4],
 [2, 4, 4],
 [3, 3, 4],
 [4, 2, 4],
 [5, 1, 4]]

duplicates_count = {}
for m in move:
    tuple_key = tuple(m)
    if tuple_key in duplicates_count:
        duplicates_count[tuple_key] += 1
    else:
        duplicates_count[tuple_key] = 1
duplicates_count

{(0, 1, 4): 1,
 (1, 2, 4): 1,
 (2, 3, 4): 1,
 (3, 4, 4): 2,
 (4, 5, 4): 1,
 (5, 6, 4): 1,
 (0, 3, 2): 1,
 (1, 4, 2): 1,
 (2, 4, 3): 1,
 (4, 4, 5): 1,
 (5, 4, 6): 1,
 (6, 4, 7): 1,
 (0, 6, 4): 1,
 (1, 5, 4): 1,
 (2, 4, 4): 1,
 (3, 3, 4): 1,
 (4, 2, 4): 1,
 (5, 1, 4): 1}

이동 중 같은 좌표에 로봇이 2대 이상 모인다면 충돌할 가능성이 있는 위험 상황으로 판단합니다. 관리자인 당신은 현재 설정대로 로봇이 움직일 때 위험한 상황이 총 몇 번 일어나는지 알고 싶습니다. 만약 어떤 시간에 여러 좌표에서 위험 상황이 발생한다면 그 횟수를 모두 더합니다.
운송 포인트 n개의 좌표를 담은 2차원 정수 배열 points와 로봇 x대의 운송 경로를 담은 2차원 정수 배열 routes가 매개변수로 주어집니다. 이때 모든 로봇이 운송을 마칠 때까지 발생하는 위험한 상황의 횟수를 return 하도록 solution 함수를 완성해 주세요.

len([count for count in duplicates_count.values() if count not in [1]])

- 2번 예제

i = 0, i = 2, i = 3이 [0, 1, 4], [1, 2, 4], [2, 3, 4] 가 같아 num + 3
i = 0, i = 1, i = 2, i = 3이 [3, 4, 4]가 같아 num + 1
i = 0, i = 2이 [4, 5, 4] [5, 6, 4] 가 같아 num + 2
i = 1, i = 3이 [4, 4, 5],[5, 4, 6]가 같아 num+2
i = 1, i = 3의 [6, 4, 7]가 같아 num + 1
따라서 9를 return 해야 합니다.

points = [[3, 2], [6, 4], [4, 7], [1, 4]]
routes = [[4, 2], [1, 3], [4, 2], [4, 3]]

def move_point(start, end, points, newpoints, move, step = 0,a = 1):
    x1, y1 = points[start - 1]
    x2, y2 = points[end - 1]
    
    if a == 1:
        move.append([step,x1,y1])
    
    while x1 != x2 or y1 != y2 :
        step += 1
        if x1 < x2:
            x1 += 1
        elif x1 > x2:
            x1 -= 1
        elif y1 < y2:
            y1 += 1
        elif y1 > y2:
            y1 -= 1
        move.append([step,x1, y1])

    newpoints[start - 1] = [x1, y1]

newpoints = [point[:] for point in points]
move = []
for i,route in enumerate(routes):
    if len(route) == 2 :
        move_point(route[0], route[1], points, newpoints, move)
    elif len(route) > 2 :
        step = 0
        a = 1
        for j in range(len(route)-1):
            move_point(route[j], route[j+1], points, newpoints, move, step, a)
            step = move[-1][0]
            a = 0

move

[[0, 1, 4],
 [1, 2, 4],
 [2, 3, 4],
 [3, 4, 4],
 [4, 5, 4],
 [5, 6, 4],
 [0, 3, 2],
 [1, 4, 2],
 [2, 4, 3],
 [3, 4, 4],
 [4, 4, 5],
 [5, 4, 6],
 [6, 4, 7],
 [0, 1, 4],
 [1, 2, 4],
 [2, 3, 4],
 [3, 4, 4],
 [4, 5, 4],
 [5, 6, 4],
 [0, 1, 4],
 [1, 2, 4],
 [2, 3, 4],
 [3, 4, 4],
 [4, 4, 5],
 [5, 4, 6],
 [6, 4, 7]]

duplicates_count = {}
for m in move:
    tuple_key = tuple(m)
    if tuple_key in duplicates_count:
        duplicates_count[tuple_key] += 1
    else:
        duplicates_count[tuple_key] = 1
duplicates_count

{(0, 1, 4): 3,
 (1, 2, 4): 3,
 (2, 3, 4): 3,
 (3, 4, 4): 4,
 (4, 5, 4): 2,
 (5, 6, 4): 2,
 (0, 3, 2): 1,
 (1, 4, 2): 1,
 (2, 4, 3): 1,
 (4, 4, 5): 2,
 (5, 4, 6): 2,
 (6, 4, 7): 2}

len([count for count in duplicates_count.values() if count not in [1]])

- 3번 예제

points = [[2, 2], [2, 3], [2, 7], [6, 6], [5, 2]]
routes = [[2, 3, 4, 5], [1, 3, 4, 5]]

def move_point(start, end, points, newpoints, move, step = 0,a = 1):
    x1, y1 = points[start - 1]
    x2, y2 = points[end - 1]
    
    if a == 1:
        move.append([step,x1,y1])
    
    while x1 != x2 or y1 != y2 :
        step += 1
        if x1 < x2:
            x1 += 1
        elif x1 > x2:
            x1 -= 1
        elif y1 < y2:
            y1 += 1
        elif y1 > y2:
            y1 -= 1
        move.append([step,x1, y1])

    newpoints[start - 1] = [x1, y1]

newpoints = [point[:] for point in points]
move = []
for i,route in enumerate(routes):
    if len(route) == 2 :
        move_point(route[0], route[1], points, newpoints, move)
    elif len(route) > 2 :
        step = 0
        a = 1
        for j in range(len(route)-1):
            move_point(route[j], route[j+1], points, newpoints, move, step, a)
            step = move[-1][0]
            a = 0

move

[[0, 2, 3],
 [1, 2, 4],
 [2, 2, 5],
 [3, 2, 6],
 [4, 2, 7],
 [5, 3, 7],
 [6, 4, 7],
 [7, 5, 7],
 [8, 6, 7],
 [9, 6, 6],
 [10, 5, 6],
 [11, 5, 5],
 [12, 5, 4],
 [13, 5, 3],
 [14, 5, 2],
 [0, 2, 2],
 [1, 2, 3],
 [2, 2, 4],
 [3, 2, 5],
 [4, 2, 6],
 [5, 2, 7],
 [6, 3, 7],
 [7, 4, 7],
 [8, 5, 7],
 [9, 6, 7],
 [10, 6, 6],
 [11, 5, 6],
 [12, 5, 5],
 [13, 5, 4],
 [14, 5, 3],
 [15, 5, 2]]

duplicates_count = {}
for m in move:
    tuple_key = tuple(m)
    if tuple_key in duplicates_count:
        duplicates_count[tuple_key] += 1
    else:
        duplicates_count[tuple_key] = 1
duplicates_count

{(0, 2, 3): 1,
 (1, 2, 4): 1,
 (2, 2, 5): 1,
 (3, 2, 6): 1,
 (4, 2, 7): 1,
 (5, 3, 7): 1,
 (6, 4, 7): 1,
 (7, 5, 7): 1,
 (8, 6, 7): 1,
 (9, 6, 6): 1,
 (10, 5, 6): 1,
 (11, 5, 5): 1,
 (12, 5, 4): 1,
 (13, 5, 3): 1,
 (14, 5, 2): 1,
 (0, 2, 2): 1,
 (1, 2, 3): 1,
 (2, 2, 4): 1,
 (3, 2, 5): 1,
 (4, 2, 6): 1,
 (5, 2, 7): 1,
 (6, 3, 7): 1,
 (7, 4, 7): 1,
 (8, 5, 7): 1,
 (9, 6, 7): 1,
 (10, 6, 6): 1,
 (11, 5, 6): 1,
 (12, 5, 5): 1,
 (13, 5, 4): 1,
 (14, 5, 3): 1,
 (15, 5, 2): 1}

len([count for count in duplicates_count.values() if count not in [1]])