[백준] 13549번: 숨바꼭질 3

문제

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

13549번: 숨바꼭질 3

 

풀이

BFS(너비 우선 탐색)를 사용해 풀었습니다.

범위 내에 이동할 수 있으면 방문 처리와 큐에 (이동 위치, 시간)을 추가합니다.

※ 두 배 이동한 경우를 우선으로 확인해야 하므로 append()가 아닌 appendleft()를 해줘야 합니다.

※ 앞서 방문한 위치는 다시 방문하지 않으므로 한 칸 이동한 경우보다 두 배 이동한 경우를 먼저 확인해야 합니다.

 

코드

파이썬

from collections import deque
import sys

input = sys.stdin.readline


def BFS():
    queue = deque()
    visited = [False] * 100001
    visited[N] = True
    queue.append((N, 0))
    while queue:
        x, t = queue.popleft()
        if x == K:
            return t
        if 0 <= (2 * x) <= 100000 and not visited[2 * x]:
            visited[2 * x] = True
            queue.appendleft((2 * x, t))
        if 0 <= (x - 1) <= 100000 and not visited[x - 1]:
            visited[x - 1] = True
            queue.append((x - 1, t + 1))
        if 0 <= (x + 1) <= 100000 and not visited[x + 1]:
            visited[x + 1] = True
            queue.append((x + 1, t + 1))


N, K = map(int, input().split())
print(BFS())