백준 13913. 숨바꼭질 (Python)

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

풀이

bfs(너비우선탐색)을 통해 해결하는 문제이다.
N에서 k까지 주어진 3가지의 이동방법(N-1,N+1,N*2)를 통해 최단거리로 이동하면서, 그 이동횟수와 이동방법을 출력해야한다.
처음엔 dp를 이용해 풀려했지만, 시간초과가 날 것 같아서 pass!

먼저 이미 왔던 길인지 확인하기 위한 li배열과, 해당위치로 오기전 이전위치를 알기위한 move배열을 만든다.
그리고 bfs를 통해 N부터 시작한다.

• 만약 현재위치(x)가 K일 경우, li[x]를 출력하고 리턴
• x-1, x+1, x*2의 방법중 0<=i<=100000이고 해당위치를 방문하지 않았다면(li[i]==0)
  deque에 추가한 뒤, move[i]=x(i번째 위치를 오기전에는 x위치)

N이 K까지 도달할 수 없는 방법은 없으므로 예외는 생략한다.(N+1만 반복해도 도달하므로)

• res배열에 K를 추가한 뒤, x=K로 선언
• x가 N과 다를 때 까지 x=move[x]를 통해 왔던길을 되돌아 가면서 res배열에 추가해준다
• 마지막으로 res배열을 반대로 출력해주면 끝!

from collections import deque
N,K=map(int,input().split())
li=[0]*(100001)
move=[0]*(100001)
res=[]
q=deque()
q.append(N)
while q:
    x=q.popleft()
    if x==K:
        print(li[x])
        break
    for i in (x-1,x+1,2*x):
        if 0<=i<=100000 and li[i]==0:
            li[i]=li[x]+1
            q.append(i)
            move[i]=x

res=[K]
x=K
while x!=N:
    res.append(move[x])
    x=move[x]
print(*res[::-1])