[백준] 1697: 숨바꼭질

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

수빈이가 5-10-9-18-17 순으로 가면 4초만에 동생을 찾을 수 있습니다.

import sys
from collections import deque
def solution():
    n, k = map(int, sys.stdin.readline().split())
    def bfs():
        visited = [0]*100001
        q = deque()
        q.append(n)
        while q:
            now = q.popleft()
            if now == k:
                return visited[now]
            for next in (now-1, now+1, 2*now):
                if 0 <= next < 100001 and not visited[next]:
                    visited[next] = visited[now] + 1
                    q.append(next)
    print(bfs())
solution()

출발 지점의 visited는 따로 처리해주지 않고 0으로 두어도 괜찮습니다.

왜냐하면 n == k인 경우(수진이와 동생의 위치가 같은 경우)는 bfs()를 실행하자마자 now == k에 걸리게 되어 0초를 반환하게 되고 나머지의 경우는모두 1초 이상이 걸리기 때문에 visited[next] = visited[now] + 1을 해주면서 최단 거리를 구하게 됩니다.