숨바꼭질 4

def BOJ13913():
  n, k = map(int, input().split())
  graph = [1e9] * 100001
  queue = []
  graph[n] = 0
  queue.append([n, 0])
  dict = {n: n}
  while queue:
    current_node, current_time = queue.pop(0)
    next_time = current_time + 1

    next_node = current_node - 1
    if 0 <= next_node <= 100000 and graph[next_node] > next_time:
      graph[next_node] = next_time
      dict[next_node] = current_node
      queue.append([next_node, next_time])

    next_node = current_node + 1
    if 0 <= next_node <= 100000 and graph[next_node] > next_time:
      graph[next_node] = next_time
      dict[next_node] = current_node
      queue.append([next_node, next_time])

    next_node = current_node * 2
    if 0 <= next_node <= 100000 and graph[next_node] > next_time:
      graph[next_node] = next_time
      dict[next_node] = current_node
      queue.append([next_node, next_time])

  print(graph[k])
  result = str(k)
  temp = k
  for _ in range(graph[k]):
    result = result + ' ' + str(dict[temp])
    temp = dict[temp]
  print(' '.join(result.split()[::-1]))


BOJ13913()

 

접근방법 : 

1. bfs를 이용하여 접근할 수 있는 모든 지점에 순차적으로 접근할 수 있게 하였다.

2. 경로에 대한 이슈가 제일 관건이었다. 아래와 같이 해결하였다.
    2-1 graph의 시간 값이 업데이트 되는 경우는 기존의 값보다 작을 때 뿐이다.
    2-2 5에서 10으로 갔다면 dict[5] = 10, 10에서 9로 갔다면 dict[10] = 9 이렇게 값이 업데이트 될때 마다 dict에 그 경로를 기록해 주자
   2-3 dict[17]의 값은 이전 시간에 있었던 곳이다. 거꾸로 따라가다 보면 출발지에 도달할 것이다.
3. graph에는 시간 값이 들어있다. 시간이 0이 될때까지 거꾸로 탐색해주면 경로를 알아낼 수 있다.

 

장애물 이였던 것 :

1. 경로를 접근하는 개념에 있어 해결방법을 떠올리지 못하고 다른 분들의 풀이를 참고하였다.

 

 

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

13913번: 숨바꼭질 4