해커를 꿈꾸는 개발자

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

www.acmicpc.net/problem/1697

문제 풀이

1697 숨바꼭질 문제는 BFS를 이용해 풀 수 있는 문제입니다. 

각 위치까지 몇초가 걸리는지에 대한 정보를 넣을 1차원 배열을 하나 만듭니다. 

그리고 현재 점을 Queue에 넣으면서 BFS를 동작시킵니다. 

BFS를 동작시킬 때, 아래 3가지 동작이 이루어지도록 하고, 이동된 위치를 Queue에 넣습니다. 

1) 1초 후에 X-1로 이동 (단, X-1이 0보다는 크거나 작아야 됩니다.)

2) 1초 후에 X+1로 이동 (단, X+1이 200000보다는 같거나 작아야 합니다.)

3) 1초 후에 2*X로 이동 (단, X*2가 200000보다는 같거나 작아야 합니다.)

그리고 이동된 위치를 Queue에 넣을 때, 해당 위치에 대한 시간정보를 넣어서, 중복 방문하지 않도록 하고, 이 시간 정보는 다음 위치를 위해 계속 사용됩니다. 

Queue에 pop할 때, pop한 위치가 동생이 있는 위치라면, 배열에서 그 위치에 있는 시간 정보를 출력하면 이 문제가 해결됩니다. 

전체 코드

import sys
from collections import deque

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

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

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

    if next == K:
        result = arr[next]
        break
    if next-1 >= 0 and arr[next-1] == 0:
        arr[next-1] = arr[next] + 1
        queue.append((next - 1))
    if next+1 <= 200000 and arr[next+1] == 0:
        arr[next+1] = arr[next] + 1
        queue.append((next + 1))
    if next*2 <= 200000 and arr[next*2] == 0:
        arr[next*2] = arr[next] + 1
        queue.append((next * 2))

print(result)