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

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

12851번: 숨바꼭질 2

---

문제 해석 : 숨바꼭질을 하는데 이동 가능한 경우는 X-1, X+1, X*2이다. 이때 가장 빠르게 K로 이동할 수 있는 경우의 수와 그 시간을 구하는 문제이다.

 

문제 풀이 : BFS를 통해서 모든 경우를 조사하면서 횟수를 검사하면 풀 수 있다.

---

풀이 코드

from collections import deque

def search(N):

    visited = [[-1, 0] for _ in range(100001)]
    answer = deque()
    answer.append(N)

    visited[N][0] = 0
    visited[N][1] = 1

    while answer:
        position = answer.popleft()

        for element in (position + 1, position - 1, position * 2):
            if 0 <= element <= 100000:
                if visited[element][0] == -1:
                    visited[element][0] = visited[position][0] + 1
                    visited[element][1] = visited[position][1]
                    answer.append(element)

                elif visited[element][0] == visited[position][0] + 1:
                    visited[element][1] += visited[position][1]

    return visited[K][0], visited[K][1]

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

time, count = search(N)
print(time)
print(count)

---

author : donghak park
contact : donghark03@naver.com

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