[코딩 테스트 연습(파이썬/Python)] 백준(BOJ) 13913번 _ 숨바꼭질 4

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

13913번: 숨바꼭질 4

[문제]

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

 

[입력]

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

[출력]

첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

둘째 줄에 어떻게 이동해야 하는지 공백으로 구분해 출력한다.

 

[아이디어]

1) queue에 위치와 지금까지의 이동을 같이 기록한다.

 

from collections import deque, defaultdict
n,k = map(int,input().split())
cnt = {n:0}
q = deque([(n,str(n))])

while q:
    now, track = q.popleft()
    if now==k:
        break
    for t in [now-1, now+1, now*2]:
        if 0<=t<=100000:
            if t in cnt:
                if cnt[t] > cnt[now]+1:
                    cnt[t] = cnt[now]+1
                    q.append((t,track + ' '+str(t)))
            else:
                cnt[t] = cnt[now]+1          
                q.append((t,track + ' '+str(t)))
                
print(cnt[k])
print(track)

위 방법으로도 풀리긴 하는데, 필요하지 않은 경로도 많이 계산하고 저장하기 때문에 메모리와 시간 효율면에서 아쉬운 점이 있다. (+ 연산의 반복)

from collections import deque
n,k=map(int,input().split())
D=[[-1,-1] for _ in range(10**5+1)]
D[n][0]=0;q=deque([n])
while q:
    x=q.popleft()
    for nx in [x+1,x-1,2*x]:
        if 0<=nx<=10**5 and D[nx][0]==-1:
            D[nx][0]=D[x][0]+1
            D[nx][1]=x
            q.append(nx)
print(D[k][0])
K=[]
while k!=n:
    K.append(k)
    k=D[k][1]
# print(K)
print(' '.join(map(str,[n]+K[::-1])))

이 방법처럼 2차원 배열에 기록해가면서, 원하는 경로에 대해서만 계산을 하는 것이 시간 효율면에서 이득이 크다.