(Python) - BOJ(12851번) : 숨바꼭질 2

https://www.acmicpc.net/problem/12851

12851번: 숨바꼭질 2

---

• 문제 : 

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 그리고, 가장 빠른 시간으로 찾는 방법이 몇 가지 인지 구하는 프로그램을 작성하시오.

 

 

 

---

• 풀이 :

bfs로 모든 경우를 탐색한다. 이 때, visited에 저장하는 값이 2개인데 하나는 최단거리이고 하나는 경우의 수이다.

경우의 수는 목표값인 M에 도달했으면서 최단거리가 일치할 때 1씩 증가시켜준다.

 

 

 

---

• 소스코드 : 

from collections import deque

if __name__ == "__main__":
    N,M = map(int,input().split())
    visited = [[-1,0] for _ in range(100001)]
    visited[N][0] = 0
    visited[N][1] = 1
    queue = deque()
    queue.append(N)
    answer = 1
    while queue:
        x = queue.popleft()
        for i in [x-1, x+1, x*2]:
            if 0 <= i <= 100000:
                if visited[i][0] == -1:
                    visited[i][0] = visited[x][0] + 1
                    visited[i][1] = visited[x][1]
                    queue.append(i)
                elif visited[i][0] == visited[x][0] + 1:
                    visited[i][1] += visited[x][1]
    print(visited[M][0])
    print(visited[M][1])