사이트 #문제: 문제유형 / 난이도

문제 링크 :

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

🔍 Inspection

문제 접근(문제 분석 → 풀이 아이디어)

🚩 FLOW

코드를 풀이할 때 적었던 플로우가 있나요?

[0] 입력 변수 입력하기

• visited[현재 위치] = [ 도착 시간 t, 출발지 cx]
  • 즉 바로 직전 출발지 → 현재위치 = 도착지을 최단 시간과 같이 1개의 배열 visited 로 관리함
  • 초기값 visied[N] = [0,N]

[1] BFS을 활용해 최단 시간 찾기

1. 출발지와 도착지(N==K) 가 같은 경우 예외 처리
2. while 문과 첫번째 for문을 통해, 같은 level(시간 t) 인 경우를 한번에 처리하기
3. 두번째 for 문으로 BFS 탐색하기

[2] 최단 시간을 가진 “경로” 출력하기

• visited 내의 출발지 cx 을 통해 최종 도착지 K 로 부터 최초 출발지 N 까지의 경로를 역추적함

  ex) 5 ,17

  visited[17] = [ 4, 18]

  visited[18] = [3, 9]

  visited[9] = [2 , 10]

  visited[10] = [1, 5 ]

  visited[5] = [0,5]

🚩제출한 코드

import sys
from collections import deque
input = sys.stdin.readline
N, K = map(int, input().split())
MAX = 100001
# answer = [] 
#[1] 최단 시간 찾기 
visited = [[MAX, MAX] for _ in range(MAX+1)]# level 기입

t= 0
next_node = [N]
q = deque([N])
visited[N] = [t,N] # 도착 시간 , 이전 node 위치 확인

#(예외처리) 출발지 = 도착지 같은 경우
if K != N : 
  while q :
    t+=1
    next_node = len(q)
    # print(F"t{t}")
    for i in range(next_node) : # 현재 level의 node개수만큼 반복
      cx = q.popleft()
      # print(f"cx {cx} , {next_node}")
      # 만약 목적 달성시 , 끝
      for nx in [cx -1 , cx+1 , cx*2]:
        if 0<= nx <= MAX and visited[nx][0]>= MAX : 
          q.append(nx)
          visited[nx] = [t, cx]   
    # 현재 q -> 다음 level 의 노드만 남아있는 상태
    # 만약 K을 도달한 경우-> 최단 시간 저장
    if visited[K][0]< MAX : 
      break
print(t)
#[2] 역추적 - 최단 시간 경우 , 경로 추적
re_visited = [K]
pt = K
while pt != N : 
  _ , pt =visited[pt]
  re_visited.append(pt)

# print(re_visited)
print(" ".join(map(str,list(reversed(re_visited)))))