[Python] 백준 1697. 숨바꼭질 (BFS)

문제 링크

Point

• 수빈이의 위치가 동생보다 큰 경우 (n >= k), 가장 빠른 경우는 계속X-1 하는 것이기에 바로print(n-k) 하면 됨
• 그게 아닌 경우, bfs로 탐색.
• 동생 찾으면 바로 탐색 중지하고 프로그램 종료.
• 이때, bfs로 하는 게 중요. dfs로 하면 시간초과 날 수 있음
  • 이유: dfs로 할 경우 동생 찾을 때까지 탐색이 끝나지 않기 때문에 탐색할 필요가 없는 매우 비효율적인 경로 여러 개를 탐색해야 됨. 그래서 시간초과 발생. 그러나 bfs는 비효율적인 경로 끝까지 가지 않고, 효율적인 경로로 동생 찾으면 탐색이 중단되기 때문에 더 효율적임.

코드

from collections import deque
import sys


def bfs():
    visited = set()
    while q:
        x, time = q.popleft()
        visited.add(x)
        if x == k:
            print(time)
            return
        for next_x in (2 * x, x + 1, x - 1):
            if next_x < k * 2 and next_x not in visited:
                q.append([next_x, time + 1])


if __name__ == '__main__':
    n, k = map(int, sys.stdin.readline().split())
    if n >= k:
        print(n - k)
    else:
        q = deque([[n, 0]])
        bfs()