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

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

13549번: 숨바꼭질 3

---

문제 해석 : N에서 K로 이동하는 방법에는 3가지가 있다. X-1, X+1, X *2 이 때 X*2로 이동할 때는 0초가 걸리고 나머지는 1초가 걸린다. 최소 이동 시간을 구하는 문제이다.

 

문제 풀이 : BFS로 모든 경우를 체크하면서 푼다. 다만 이때 0초로 이동하는 것이 가장 우선 체크 되어야 하기 때문에 항상 가장 처음에 위치 시킨다. 또한 무한 루프를 방지하기 위해서 0인 경우는 예외로 처리한다.

---

풀이 코드

from collections import deque

def search(N):

    visited = [0] * 100001
    Q = deque()
    Q.append(N)

    while Q:
        position = Q.popleft()
        if position == K:
            return visited[position]

        for next_position in (position + 1, position - 1, position * 2) :

            if 0 <= next_position < 100001:
                if visited[next_position] == 0:
                    if next_position == position * 2 and next_position != 0:
                        visited[next_position] = visited[position]
                        Q.appendleft(next_position)
                    else:
                        visited[next_position] = visited[position] + 1
                        Q.append(next_position)


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

---

author : donghak park
contact : donghark03@naver.com

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