BOJ 1697: 숨바꼭질 [Python 3, BFS]

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

1697번: 숨바꼭질

BFS를 이용한 문제를 풀어봤다.

import sys
from collections import deque

def bfs():
    q=deque()
    q.append(n)
    while q:
        num=q.popleft()
        if num==k:
            print(loc[k])
            break
        for i in (num-1,num+1,num*2):
            if 0<=i<=200000 and loc[i]==0:
                loc[i]=loc[num]+1
                q.append(i)
                
loc=[0]*200001
n,k=map(int,input().split())

bfs()

 

bfs는 수빈이의 위치를 queue에 넣고, 하나씩 pop하면서

수빈이 위치를 num이라고 하면, num-1, num+1, 2*num으로 위치를 이동시키면서 초를 센다.

찾게 될 경우, 출력하는 함수이다.