[백준] 1697번(숨바꼭질)

백준 1697번

처음 제출한 코드(메모리 초과)

from collections import deque

n, k = map(int, input().split())

def bfs():
  queue = deque()
  queue.append([0, n])
  
  while queue:
  
    times, value = queue.popleft()

    if value==k:
      print(times)
      return
      
    times += 1
    values = [value - 1, value + 1, value*2]
    
    for i in range(len(values)):
      queue.append([times, values[i]])

bfs()

◼️ bfs를 활용한 문제풀이

• 주어진 값에 모든 경우의 수의 계산을 적용하여 그 값을 depth와 함께 queue에 넣고, pop(0)되는 값이 k와 동일할 경우 times를 출력한 후 return
• 같은 값에 여러번 접근하는 경우를 차단하는 코드를 추가해주지 않아 메모리초과 발생

/

최종 제출 코드

from collections import deque

n, k = map(int, input().split())
visited = [0]*100001

def bfs():
  queue = deque()
  queue.append(n)
  
  while queue:
  
    value = queue.popleft()
    
    if value==k:
      print(visited[value])
      return

    values = [value - 1, value + 1, value*2]
    for i in values:
      # 인덱스가 범위내여야 하며
      if i >= 0 and i <= 100000:
        # 방문했던 곳의 depth 값을 바꾸는건 허용되지 않는다
        if visited[i] == 0:
          visited[i] = visited[value]+1
          queue.append(i)

bfs()

◼️ visited 리스트를 이용해 depth를 업데이트하고, 방문 이력이 있는지도 검사

• visited 리스트의 인덱스 범위는 n, k 값의 범위와 동일하게 설정
• i 값이 범위 내인지 확인하고, 방문이력이 없으면 visited 리스트를 업데이트
• k와 동일한 값이 pop(0)되는 순간 visited[queue.pop(0)](depth)를 출력하고 함수 종료