[Python] 백준 12851번: 숨바꼭질2

# 문제 내용

백준 12851번: 숨바꼭질2

12851번: 숨바꼭질 2

 

# 알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

 

# 풀이

from collections import deque
import sys

input = sys.stdin.readline
MAX_SIZE = 100001 # 가능한 n,k의 최대값 - 1

# n : 수빈 위치, k : 동생 위치
n, k = map(int, input().split())

q = deque()
q.append(n)

# k까지 가장 빨리 찾는 방법을 담을 배열
visited = [-1] * MAX_SIZE
visited[n] = 0 # 현위치는 방문했으므로

# 가장 빠른 시간으로 찾는 방법의 수
min_cnt = 0;

# 걷는 경우 + 1, -1
# 순간 이동을 하는 경우 2 * 현위치

while q:
  now = q.popleft()

  # 동생 위치에 도달했다면
  if now == k :
    min_cnt += 1

  # 방향 이동 경우의 수
  # +1 걷기 / -1 걷기 / now * 2 순간이동
  for next in [now + 1, now - 1, now * 2]:
    # 위치가 이동할 수 있는 범위 안에 있다면
    if 0 <= next < MAX_SIZE:
      # 방문하지 않았거나 / 방문했어도 현재 시간보다 더 많거나 같다면 최소 시간을 교체
      if visited[next] == -1 or visited[next] >= visited[now] + 1:
        visited[next] = visited[now] + 1
        # 방문 위치를 큐에 추가
        q.append(next)

print(visited[k])
print(min_cnt)

 

# References

https://chaemi720.tistory.com/213

[백준] 12851. 숨바꼭질 2 - Python