📚 1697 - 숨바꼭질

숨바꼭질

이해

현재 점 : N을 기준으로
동생 점 : K로 가면 된다.

next_n = N (+- 1) or (*2)

next_n이 K에 도착하면 몇 초인지 출력하면 된다.
이는 bfs로 시작 점을 기준으로 탐색을 진행하며, 동생의 점에 도착했을 때 바로 종료하면 된다. (작은 것부터 찾다가 나오면 종료하면 되지 큰 것까지 찾을 필요가 없기 때문)

소스

import sys
from collections import deque

read = sys.stdin.readline

n, k = map(int, read().split())


# bfs

def bfs():
    queue = deque()
    queue.append((n, 0))
    visited = [False] * 100010
    visited[n] = True

    while queue:
        x, cnt = queue.popleft()

        if x == k:
            # bfs 특징 상 작은 것부터 검색 하니, 나오면 종료하면 된다.
            print(cnt)
            break

        for move_data in (x - 1, x + 1, 2 * x):
            if 0 <= move_data <= 100000 and not visited[move_data]:
                visited[move_data] = True
                queue.append((move_data, cnt + 1))


bfs()

채점 결과