[BOJ] 1697 숨바꼭질

www.acmicpc.net/problem/1697

1697번: 숨바꼭질

풀이

• deque를 사용한 bfs로 품

  from collections import deque
  
  def bfs(start, end):
      cnt = 0
      # [현재 위치, 현재까지 걸린 시간] pair
      queue = deque([[start, cnt]])
      # 문제 조건에 0~100000 위치까지로 명시됨.
      # 방문안한 위치만 queue에 값 추가해서 탐색
      visited = [False] * 100001
      
      while queue:
          pos, cnt= queue.popleft()
          if visited[pos] == False:
              visited[pos] = True
              if end == pos:
                  return cnt
              else:
                  cnt += 1
                  if pos * 2 <= 100000:
                      queue.append([pos*2, cnt])
                  if pos+1 <= 100000:
                      queue.append([pos+1,cnt])
                  if pos-1 >= 0:
                      queue.append([pos-1, cnt])
      return cnt
  s, e = map(int, input().split())
  print(bfs(s, e))