백준 1697번 바로가기

내 풀이

# 입력
import sys
n, k = map(int, sys.stdin.readline().split())

from collections import deque
queue = deque([n])

visitedList = [False]*100001
count = 0

# 처리
while queue:
  if k in queue:
    print(count)
    break
  count += 1
  for _ in range(len(queue)):
    temp = queue.popleft()
    if not visitedList[temp]:
      next = [temp-1,temp+1,temp*2]
      for n in next:
        if 0<=n<=100000 and visitedList[n]==False:
          queue.append(n)
      visitedList[temp] = True

CODE REVIEW

  1. BFS를 응용한 문제.
  2. 100,001개의 node을 가진 graph를 구해놓고 최소경로를 구하는 방법도 있겠지만, 메모리나 시간적으로 매우 비효율적이다.
  3. 따라서 초기 queue에 n을 집어놓고 BFS로 나아가면서 k가 queue에 등장하는지 확인하는 방법으로 구현했다.
  4. count를 구현하는 과정에서 꽤나 애를 먹었다… 처음에는 count=[0]*100001 count[n]=count[temp]+1로 두고 풀었는데, count를 탐색하는 과정에서 시간을 많이 잡아먹어서 아예 구조를 바꾸었다.
  5. for _ in range(len(queue))로 BFS 한 층이 다 마무리 될 때까지 loop를 돌리는 방식으로, loop마다 count를 1씩 올려가며 탐색을 진행하니 시간 문제 없이 해결되었다.