[백준]1697 숨바꼭질 Python

[백준]1697 숨바꼭질 Python

왜 이 문제가 BFS,DFS 문제인지 생각해 볼 필요가 있다. 먼저, 수빈이가 이동할 수 있는 경우는 세가지다.

x+1,x-1,2*x

이렇게 세 가지의 경우에 따라, 횟수가 진행되는 만큼 그래프가 그려진다. 따라서, 완전탐색 문제로 답을 찾아가야한다.
코드를 짜면서 주의해야 하는 점은 for문 안에 저 세가지 중 2*x를 먼저 두어야한다.
힌트에서도 "수빈이가 5-10-9-18-17 순으로 가면 4초만에 동생을 찾을 수 있다." 라고 되어 있다.
그렇기에, 제일 빠르게 도달할 수 있도록 2배를 먼저 두고 코드를 짜야한다.

import sys
from collections import deque
sys.stdin=open("input.txt")
n,k=map(int,input().split())

visited=[-1 for _ in range(100001)] #횟수를 저장할 배열

def bfs(x,y):
    visited[x]=0
    q=deque()
    q.append(x)

    while q:
        v=q.popleft()
        if v==y:
            print(visited[y])
            return 0
        for i in (2*v,v-1,v+1):
            if 0<=i<=100000 and visited[i]==-1:
                visited[i]=visited[v]+1
                q.append(i)

bfs(n,k)