PROGRAMMERS 숫자 타자 대회 python

숫자마다 for문을 돌면서 큐를 갱신함.
왼손이 움직이는 경우와, 오른손이 움직이는 경우를 따로 계산.
손의 위치가 같은 경우, 비용이 가장 작은 값만 저장.
마지막 큐에서 가장 작은 값 리턴.

처음에는 다익스트라로 시도를 했는데, 시간 초과가 났다. 좀 더 고민해보면 이 문제는 그리디로 해결 가능하다. 근데 그리디로 코드를 바꿔도 시간 초과가 났다. move 함수 부분을 원래는 그래프 탐색으로 구현했는데, 간단하게 하드코딩이 가능했다. (x값 차이 + y값 차이)에 움직인 횟수를 더해주면 되는데, 움직인 횟수는 x값 차이와 y값의 차이의 최대값으로 쉽게 구할 수 있다. 제자리에 있는 경우에는 1을 더해주면 된다.

풀이 코드

def solution(numbers):
    n = len(numbers)
    g = [[1,3],[0,0],[1,0],[2,0],[0,1],[1,1],[2,1],[0,2],[1,2],[2,2]]
    dp = [[0 for _ in range(10)] for _ in range(n)]
    q = [(0, 0, 4, 6)]
 
    def move(s, w, e):
        sx, sy = g[s]
        ex, ey = g[e]
        if e==w: return 0
        return abs(sx-ex)+abs(sy-ey) + max(abs(sx-ex), abs(sy-ey), 1)
    
    ans = 10**8
    q1, q2 = [[0, 4, 6]], []
    for n in numbers:
        n = int(n)
        for t, lh, rh in q1:
            dt = move(lh, rh, n)
            if dt:
                for i, q in enumerate(q2):
                    if (q[1] == n and q[2] == rh) or (q[1] == rh and q[2] == n):
                        q2[i][0] = min(q2[i][0], t+dt)
                        break
                else: q2.append([t+dt, n, rh])
 
            dt = move(rh, lh, n)
            if dt:
                for i, q in enumerate(q2):
                    if (q[1] == n and q[2] == lh) or (q[1] == lh and q[2] == n):
                        q2[i][0] = min(q2[i][0], t+dt)
                        break
                else: q2.append([t+dt, lh, n])
        q1, q2 = q2, []
    for q in q1: ans = min(ans, q[0])
    return ans