[연습 문제] 숫자 타자 대회 ( 파이썬 )

문제 설명

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

프로그래머스

문제 풀이

• 번호에서 다른 번호로 이동할 때 드는 가중치들 미리 계산 (dist_num 함수)
• 각 단계별(numbers 각 자리수) 탐색 시 생성 될 수 있는 가중치들을 계산
  • 왼손을 움직일 경우 가중치는 d[left][num] , 큐에 담을 수는 num,right 
  • 오른손을 움직일 경우 가중치는 d[right][num] , 큐에 담을 수는 left,num
• 따로 조건을 달지 않을 경우 생성되는 경우의 수는 2^n 이고 최대 100,000의 길이이므로 예외를 둬야함
  • 최단거리 알고리즘을 활용해봄
  • 각 자릿수를 행으로 두는 거리 기록을 사용
  • dist => [n자릿수][ left가 움직일 수 있는 10가지 ] [ right가 움직일 수 있는 10가지 ]
  • 탐방할 가중치가 기록 값보다 클 경우 패스하는 것으로 예외 처리함 

 

소스 코드

from collections import deque
import heapq

def dist_num(): 		#각 번호들의 이동 가중치 계산 함수
    dx = [0,0,-1,1,1,1,-1,-1]
    dy = [-1,1,0,0,1,-1,1,-1]
    cell = [[0]*3 for i in range(4)]
    for i in range(3):
        for j in range(3):
            cell[i][j] = i*3+j+1
    cell[-1][0],cell[-1][2] = 11,11
    dist = [[100]*10 for i in range(10)]
    for i in range(4):
        for j in range(3):
            if cell[i][j]>10:
                continue
            t = cell[i][j]
            q = deque()
            q.append((0,i,j))
            dist[t][t]=1
            while(q):
                cnt,x,y = q.popleft()
                cur = cell[x][y]
                for k in range(8):
                    nx = x + dx[k]
                    ny = y + dy[k]
                    if nx<0 or ny<0 or nx>=4 or ny>=3:
                        continue
                    next = cell[nx][ny]
                    move = 2 if k<4 else 3
                    if next==11:
                        continue
                    if dist[t][next]<cnt+move:
                        continue
                    dist[t][next]= cnt+move
                    q.append((cnt+move,nx,ny))
    return dist
    

def solution(numbers):
    INF = int(1e9)
    answer = INF
    numbers = list(map(int,numbers))
    n=len(numbers)
    d=dist_num()
    distant = [[[INF]*10 for i in range(10)] for j in range(n+1)]
    distant[0][4][6] = 0
    q = []
    heapq.heappush(q,(0,0,4,6))
    while(q):
        w, next, left, right = heapq.heappop(q)
        if next == n:
            return w
        num = numbers[next]

        if num in [left,right]:
            if distant[next+1][left][right]>w+1:
                distant[next+1][left][right]=w+1
                heapq.heappush(q,(w+1,next+1,left,right))
                
        else:
            if  distant[next+1][num][right]>w+d[left][num]:
                distant[next+1][num][right]=w+d[left][num]
                heapq.heappush(q,(w+d[left][num],next+1,num,right))
            if  distant[next+1][left][num]>w+d[right][num]:
                distant[next+1][left][num]=w+d[right][num]
                heapq.heappush(q,(w+d[right][num],next+1,left,num))

    return answer
            

print(solution("1756"))

 

오답노트

• 현재 자리에서 다음 자리로의 거리는 미리 구하기 가능(탐색이든 수학적 접근이든)
• 시간 초과의 관건이 되는 것은 탐색 가지 수 
  • 각 자리 수마다 왼손으로 누를 지 오른손으로 누를 지 선택 해야 하므로 총 탐색을 한다면 2^100,000이 나옴
  • 이것을 줄이기 위해 처음 생각한 것은 힙큐
  • 최단 거리 알고리즘 접목 시켜서 다음으로 탐색할 숫자까지의 가중치가 현재 탐색+dist보다 크다면 값을 업데이트, 그렇지 않다면 continue
• 이렇게 했더니 일단 테케에서 시간 초과는 안뜸. 틀린 이유 찾아보기 ing

왼손 오른손으로 탐색한다는 것을 왼손은 0 오른손은 1로만 지정해서 틀림