[알고리즘][Python] 백준 1697 숨바꼭질 문제 풀이

문제 출처 : www.acmicpc.net/problem/1697

1697번: 숨바꼭질

---

문제 해석 : 숨바꼭질을 하는데 있어서 x+1, x-1, x*2로 이동하면서 이를 찾는 문제이다.

 

문제 풀이 : BFS 알고리즘으로 해결 가능하다. 좌표를 찾든 가능한 모든 경우의 방문여부 체크 배열을 만든 후에 3가지 경우에 대해서 계속 해서 검사를 하면서 이동하는 알고리즘을 통해서 문제 해결이 가능하다.

---

풀이 코드

from collections import deque

L = 100001

def search(arr, N, K):
    Q = deque()
    Q.append(N)

    while Q:
        x = Q.popleft()

        if x == K:
            return arr[x]

        for j in (x + 1, x - 1, x * 2):
            if (0 <= j < L) and arr[j] == 0:
                arr[j] = arr[x] + 1
                Q.append(j)


N, K = map(int, input().split())
arr = [0] * L

answer = search(arr, N, K)
print(answer)

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.