백준 13913 [숨바꼭질4] 파이썬

https://www.acmicpc.net/problem/13913

 

생각보다 쉽지 않았다...ㅠ 

#백준 13913 숨바꼭질
from collections import deque

N,K=map(int,input().split())
if K<N: #K가 N보다 작은경우 --> 빼기 밖에 없으므로 그냥 출력
    lst=[i for i in range(N,K-1,-1)]
    print(len(lst)-1)
    print(*lst)
elif N==K: # K와 N이 같은 경우 그냥 출력
    print(0)
    print(N)
else: #K가 N보다 큰 경우
    dic=dict()
    visited=[-1]*(2*K+2)
    q=deque()
    q.append(N)
    dic[N]=-10
    visited[N]=0
    while q: #BFS를 이용하면 정답을 찾은순간이 무조건 최소값이 보장된다.
        curr_pos=q.popleft()
        if curr_pos!=K:
            if curr_pos !=0 and curr_pos*2 < 2*(K+1) and visited[curr_pos*2]==-1: #  곱하기 두배
                dic[curr_pos*2]= curr_pos
                visited[curr_pos*2]=visited[curr_pos]+1
                q.append(curr_pos*2)
            if visited[curr_pos+1]==-1: # 더하기 1
                dic[curr_pos+1]=curr_pos
                visited[curr_pos+1]=visited[curr_pos]+1
                q.append(curr_pos+1)
            if curr_pos>0 and  visited[curr_pos-1]==-1: # 빼기 1
                dic[curr_pos-1]=curr_pos
                visited[curr_pos-1]=visited[curr_pos]+1
                q.append(curr_pos-1)
        elif curr_pos==K: #숨바꼭질 찾은경우 딕셔너리를 통해 정답 --> 이전 값 --> 이전 값 --> ... --> 초기 값 순으로 순서 확인 가능
            print(visited[curr_pos])
            lst=[]
            val=K
            while val!=-10:
                 lst.append(val)
                 val=dic[val]
            lst.reverse()
            print(*lst)
            break

처음에 큐를 여러개 생성해서 해결하려고 하였으나, 메모리초과가 발생하여, 딕셔너리로 해결하였다.

연결리스트처럼 이전값을 저장하여 사용하는 방식으로 코드 작성하니 시간이 적게 소모되었다.