백준 17071 숨바꼭질 5

haruponea·2021년 3월 25일
0

BOJ

목록 보기
26/41

문제 링크https://www.acmicpc.net/problem/17071

풀이
처음에 보면 그냥 단순히 bfs를 한번 돌리고 k를 이동시키며 비교하면 되는 줄 알았다. 하지만 단순한 bfs와는 다르게 **이미 방문했던 칸을 또 방문 할 수 있다는 점**이 중요하다. 그럼 이 중복된 방문을 어떻게 처리하느냐가 포인트인데 이미 방문 했던 위치는 2초마다 다시 방문할 수 있다는 점을 인지해야 했다. 현재 위치를 cur 이라고 하면 1초 뒤에는 cur+1, 또 다시 1초 뒤에는 (cur+1-1)로 다시 cur에 돌아온다!

짝수 번째 칸에 짝수(홀수)시간에 방문했다면 홀수(짝수)시간에 다시 방문할 수 있다. a가 짝수일때 a칸에서 시작한다면 a를 두 배한 2*a에서 다시 a로 돌아오는 과정이 총 a+1초(홀수)만큼 걸리기 때문에 짝수칸은 처음 도착한 짝수시간, 처음 도착한 홀수 시간이 모두 저장된다.

홀수 번째 칸에 짝수(홀수)시간에 도착했다면 홀수(짝수)시간에 다시 방문할 수 없다. b가 홀수일때 b칸에서 시작한다면 b를 두 배한 2*b에서 다시 b로 돌아오는 과정은 총 b+1초(짝수)만큼 걸리기 때문에 처음 도착한 시간만 기록하면 된다.

이론적으론 위와 같지만 어차피 k를 순회할때 방문하지 않은 칸을 제외하기 위한 목적으로 board에 -1이 저장되어있다면 제외시키기 때문에 따로 구분하지 않고 순회하면 된다.

Python

from collections import deque
import sys
n, k = map(int, sys.stdin.readline().split())
q = deque()
q.append((n, 0))
board = [[-1] * 500001 for _ in range(2)] # 0 even, 1 odd
board[0][n] = 0
while q:
    cur, is_even = q.popleft()
    for i in [cur + 1, cur - 1, cur * 2]:
        if 0 <= i <= 500000 and board[1 - is_even][i] == -1:
            board[1-is_even][i] = board[is_even][cur] + 1
            q.append((i, 1-is_even))
possible = False
t = 0
while k <= 500000:
    if t % 2 == 0:
        if board[0][k] != -1 and t >= board[0][k]:
            possible = True
            break
    else:
        if board[1][k] != -1 and t >= board[1][k]:
            possible = True
            break
    t += 1
    k += t
if possible:
    print(t)
else:
    print(-1)

0개의 댓글