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

문제

백준 - 12851번: 숨바꼭질2

분석

수빈이의 현재 점 N과 동생의 점 K가 주어졌을 때, 현재 수빈이가 X에 위치한다면
수빈이는 1초 후에 X-1 또는 X+1 또는 2 * X의 위치로 이동할 수 있다.
이때 동생을 찾을 수 있는 가장 빠른 시간이 몇 초인지, 그 방법이 몇 가지 인지 구하는 문제이다.

어느 지점까지 도달하기 위해 최소를 구하는 문제에 DP를 생각해 볼 수도 있겠지만, DP는 방향이 딱 한쪽으로 정해진 경우에 적용할 수 있다. 때문에 BFS를 고려하면 되는데, 평소 그래프에서 풀던 BFS에서 응용해주면 가장 빠른 시간을 쉽게 구할 수 있고, 이는 숨바꼭질에서 적용하면 된다.

이 문제는 하나 더 고려해주어야 하는게 가장 빠른 시간으로 찾는 방법이 몇 가지인지 까지 구해야한다.
때문에 재방문이 가능할 경우를 고려해야한다. 재방문이 가능할 경우는 방문하려는 곳이 현재 시간에서 1초를 더했을 경우보다 크거나 같을 때이다. (그래야 더 작은 시간으로 갱신이 가능하다)

코드

해결언어 : Python

import sys
input = sys.stdin.readline

from collections import deque
MAX = 10**5
n, k = map(int, input().split())
visited = [False]*(MAX+1)
time = [0]*(MAX+1)
def in_range(x):
    return 0 <= x <= MAX

def bfs():
    global fastest, cnt
    q = deque([n])
    visited[n] = True
    time[n] = 0
    while q:
        x = q.popleft()
        if x == k:
            fastest = time[x]
            cnt += 1
            continue
        for nx in [x-1, x+1, 2*x]:
            if in_range(nx) and (not visited[nx] or time[nx] >= time[x]+1):
                visited[nx] = True
                time[nx] = time[x]+1
                q.append(nx)
    
fastest = -1
cnt = 0
bfs()
print(fastest)
print(cnt)

끝으로..

BFS를 적용하는 것까지는 쉽게 했는데, 재방문을 고려해야 하는 것을 못해서 헤맸다.