문제

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

소스코드1

import sys
from collections import deque
input = sys.stdin.readline
if __name__ == "__main__":
    n, k = map(int, input().split())
    visited = [-1 for _ in range(100001)]
    visited[n] = 0
    q = deque()
    q.append([n,str(n)])

    while q:
        x,tmp = q.popleft()
        if x == k:
            print(visited[k])
            print(tmp)
            break
        for i in [x-1,x+1,x*2]:
            if 0 <= i < 100001:
                if visited[i] == -1:
                    visited[i] = visited[x] + 1
                    q.append([i,tmp +' '+ str(i)])

소스코드2(개선)

import sys
from collections import deque
input = sys.stdin.readline
if __name__ == "__main__":
    n, k = map(int, input().split())
    visited = [-1] * 100001 #최단경로 탐색
    idx = [0] * 100001 #거쳐온 경로 체크
    visited[n] = 0
    q = deque()
    q.append(n)

    def check(k):
        res = [k]
        i = k
        for _ in range(visited[k]):
            res .append(idx[i])
            i = idx[i]
        print(' '.join(map(str,res[::-1])))


    while q:
        x = q.popleft()
        if x == k:
            print(visited[k])
            check(x)
            break
        for i in [x-1,x+1,x*2]:
            if 0 <= i < 100001:
                if visited[i] == -1:
                    visited[i] = visited[x] + 1
                    q.append(i)
                    idx[i] = x

설명

• 소스코드1 (개선전)
  최단경로를 구하는 탐색을 할 때 거쳐온 경우의 수를 같이 데리고다니면서(?) 탐색해주고 최단경로에 도달했을 때 출력해준다.

• 소스코드2 (개선후)
  시간이 대략 30배정도 줄어들었다 ;;
  거쳐온 경로를 저장하는 DP 자료구조를 하나 추가해주고 거기에 거쳐온 경로를 저장해준다.
  최단 경로를 찾으면 최단경로의 갯수 만큼 반복문을 돌려주어 거쳐온 경로를 탐색해주고 map과 join을 이용하여 문자열로 변경해준 후 한 칸 띄어쓰기하도록 하여 출력해준다.

후기

내가 구하려는 값을 메모이제이션 해주자