이번 문제는 BFS를 통해 해결하였다. 전에 풀어보았던 숨바꼭질과 다른 점이 있다면 동생이 매 시간마다 자리를 옮기는 점이다. 이 때문에 이전처럼 방문처리를 하게 되면 동생을 잡을 수 없는 경우가 발생한다. 그래서 우선 방문처리를 하지 않고, 구현해보았다. 결과는 당연히 시간초과가 발생하였다. 가지치기가 아예 적용되지 않았기 때문에 당연한 결과였다.

다른 방법에 대해 고민을 계속 해보았지만 도저히 가지치기를 할 방법이 생각나지 않았다. 그래서 풀이 방법에 대한 힌트를 검색으로 얻었고, 그 방법대로 풀이하였다. 접근 방법은 다음과 같다.

1차원 리스트로 방문처리를 하면 방문했던 정점에 다시 방문해야 될 때, 방문할 수 없게 된다. 그래서 현재 시간이 홀수일 때와 짝수일 때의 방문을 따로 관리하는 것이다. 만약 방문처리를 하지 않는다면, 3초라는 시간에 8번 정점에 도착했다고 했을 때, 5, 7, 9, .. 초에 계속해서 그 정점에 방문할 수 있게 된다. 2초라는 시간에 3번 정점에 도착했다면, 4, 6, 8, .. 초에 계속해서 그 정점에 방문할 수 있게 된다. 이를 이용하여 현재 시간이 홀수일 때, 홀수 방문처리가 되어있다면 큐에 넣지 않고, 짝수일 때, 짝수 방문 처리가 되어있다면 큐에 넣지 않는 방식으로 접근하였다.

Code

from collections import deque
n, k = map(int, input().split())
dw, dt = [1, -1, 0], [1, 1, 2]
def bfs():
    global k
    q = deque()
    q.append(n)
    visited = [[False for _ in range(500001)] for _ in range(2)]
    visited[0][n] = True
    flag = 0
    time = 0
    while q:
        if k > 500000:
            return -1
        if visited[flag][k]:
            return time
        new_q = deque()
        flag = 1-flag
        for cur in q:
            for i in range(3):
                nxt = (cur+dw[i])*dt[i]
                if 0 <= nxt < 500001 and not visited[flag][nxt]:
                    visited[flag][nxt] = True
                    new_q.append(nxt)
        time += 1
        k += time
        q = new_q
    return -1
print(bfs())