[백준/파이썬] 13549번 숨바꼭질 3

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

13549번: 숨바꼭질 3

이 문제는 0-1 bfs 문제이다.

 

0-1 bfs란?? 그래프의 간선에서 가중치가 0과 1로만 이루어진 bfs 문제를 말한다!

이 문제가 해당 케이스이다.

 

-1, +1, *2 위치를 체크하는 것은 bfs와 다를 바 없으나,

 

가중치가 0인 간선이, 가중치가 1인 간선보다 더 앞에 삽입되어야 한다!

 

가중치가 0이라는 것은, 아무 cost가 없다는 것을 의미하기 때문에 가장 효율적이라고 볼 수 있다.

 

 즉, 가중치 0인 간선을 appendleft()를 이용해 삽입하거나, 3개의 if문 중 제일 첫번째 순서에 작성해줘야 한다.

import sys
#sys.setrecursionlimit(10**6)
input = sys.stdin.readline
from collections import deque

def main():  
  print(bfs())
  
def bfs():
  ans = 0
  while len(q) > 0 :
    ord = q.popleft()
    pos = ord[0]
    cnt = ord[1]
    
    visited[pos]= True
        
    if pos == k:
      ans = cnt
      break
    
    if pos*2 >= 0 and pos*2 < 100001 and not visited[pos*2]:
      q.append([ pos *2, cnt ])

    if pos-1 >= 0 and pos-1 < 100001 and not visited[pos-1]:
      q.append([pos - 1, cnt + 1 ])
        
    if pos+1 >= 0 and pos+1 < 100001 and not visited[pos+1]:
      q.append([ pos + 1, cnt + 1 ])
      
    
  return ans
  
if __name__ == "__main__":
  n,k = map(int,input().split())
  q = deque()
  visited = [False] * 100010
  q.append([n,0])
  
  main()