해커를 꿈꾸는 개발자

파이썬 / BOJ 백준 알고리즘 / 13549번 숨바꼭질 3 - BFS

www.acmicpc.net/problem/13549

문제 풀이

13549번 숨바꼭질 3 문제는 BFS로 풀 수 있는 문제입니다. 

아래 1697번 숨바꼭질의 약간 변형된 문제입니다. 

아래 숨바꼭질과 다른 점은 2*X에 가중치를 주어 appendleft() 함수를 사용하고, queue에서 먼저 탐색되도록 합니다. 

그리고 2*X로 탐색된 곳은 0초가 걸리기 때문에, 시간 정보를 넣을 때에는 이전의 시간 정보와 동일하게 넣습니다. 

이렇게 한다면 목적지까지의 가장 빠른 시간을 구할 수 있습니다.

zidarn87.tistory.com/248

전체 코드

import sys
from collections import deque


N,K = map(int, sys.stdin.readline().split())
arr = [0]*200001
visit = [False]*200001

queue = deque()
queue.append((N))

result = 0
while queue:
    next = queue.popleft()

    if next == K:
        result = arr[next]
        break
    
    # *2
    if next*2 <= 100000 and visit[next*2] == False:
        arr[next*2] = arr[next]
        queue.appendleft((next * 2))
        visit[next*2] = True
    # -1
    if next-1 >= 0 and visit[next-1] == False:
        arr[next-1] = arr[next] + 1
        queue.append((next - 1))
        visit[next - 1] = True
    
    # +1
    if next+1 <= 100000 and visit[next+1] == False:
        arr[next+1] = arr[next] + 1
        queue.append((next + 1))
        visit[next + 1] = True


print(result)