[백준] 12851번 숨바꼭질 2

💡문제접근

• 동생의 지점으로 이동할 때 걸리는 최단 시간, 그리고 그 최단 시간으로 찾는 방법이 몇 가지인지를 모두 구하는 문제다.
• visited 배열을 만들어 방문 여부를 따지고 만약 동생의 위치 K에 더 빠른 시간에 도달할 수 있는 경우가 있다면 해당 경우도 고려해준다.

💡코드(메모리 : 37708KB, 시간 : 352ms)

from collections import deque
import sys
input = sys.stdin.readline

N, K = map(int, input().strip().split())
visited = [-1] * 100001
ans = 0

def BFS(N):
    global ans
    queue = deque()
    queue.append(N)
    visited[N] = 0
    while queue:
        v = queue.popleft()

        if v == K:
            ans += 1
        for i in [v-1, v+1, v*2]:
            # 점 N의 범위 : 0 ≤ N ≤ 100,000
            if 0 <= i <= 100000:
                # 방문하지 않았거나 이미 더 빠른 경로로 진입이 가능한 경우
                if visited[i] == -1 or visited[i] >= visited[v] + 1:
                    visited[i] = visited[v] + 1
                    queue.append(i)
    return ans, visited[K]

result = BFS(N)
print(result[1])
print(result[0])

💡소요시간 : 31m