1. 문제 설명

숨바꼭질 5

2. 문제 분석

동생의 좌표가 시간이 지나면서 움직이기 때문에 위치가 계속 변한다. 또한 수빈이가 움직이는 +1 -1 연산으로 visited 하나 만으로는 중복 여부를 확인할 수 없다. 홀수, 짝수 여부에 맞춰 두 개의 visited를 사용해야 한다.

• 홀수 짝수 여부를 따로 카운트해주어야 함을 몰라서 시간 초과를 풀지 못했다.

• 문제 별로 제시되는 상황에 따라 일단 수학적으로 접근해보자.

3. 나의 풀이

from collections import deque

n, k = map(int, input().split())

visited = [[False for _ in range(500001)] for _ in range(2)]
# visited[0]: 짝수, visited[1]: 홀수 시간에 방문 여부 체크

queue = deque()
queue.append([n, 0, k, 0])
# 0초: 짝수 시간 수빈 n 노드, 동생 k 노드 위치
visited[0][n] = True
reachable = False
while queue:
    cur_node, time, goal, check = queue.popleft()
    if goal > 500000: break
    # 동생 위치 50만 이상 시 X
    if visited[check][goal]:
        reachable = True
        break
        # 홀수 짝수 차례에서 이미 동생의 위치를 방문한 적이 있다면 만날 수 있다.

    if check == 1: next_check = 0
    else: next_check = 1
    # 시간 홀짝 여부에 따라 방문 여부 따로 체크한다.

    offsets = [-1, 1, cur_node]
    next_time = time + 1
    next_goal = goal + next_time
    for offset in offsets:
        next_node = cur_node + offset

        if next_node < 0 or next_node > 500000: continue

        # 방문 가능한 노드이고 다음 check(즉 지금 홀 -> 다음 짝, 지금 짝 -> 다음 홀)에서 미방문한 노드이면
        if not visited[next_check][next_node]:
            visited[next_check][next_node] = True
            queue.append([next_node, next_time, next_goal, next_check])

if reachable: print(time)
else: print(-1)