[백준/17071] 숨바꼭질 5 (Python)

Problem : https://www.acmicpc.net/problem/17071

17071번: 숨바꼭질 5

 

Difficulty : Platinum 5

 

Status : Solved

 

Time : 00:40:59

 

---

 

문제 설명

 

 

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 동생은 항상 걷기만 한다. 동생은 항상 매 초마다 이동을 하며, 이동은 가속이 붙는다. 동생이 이동하는 거리는 이전에 이동한 거리보다 1을 더한 만큼 이동한다. 즉, 동생의 처음 위치는 K, 1초가 지난 후 위치는 K+1, 2초가 지난 후 위치는 K+1+2, 3초가 지난 후의 위치는 K+1+2+3이다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 동생을 찾는 위치는 정수 좌표이어야 하고, 수빈이가 0보다 작은 좌표로, 50만보다 큰 좌표로 이동하는 것은 불가능하다.

 

 

입력 및 출력

 

입력

 

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

 

출력

 

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다. 수빈이가 동생을 찾을 수 없거나, 찾는 위치가 500,000을 넘는 경우에는 -1을 출력한다.

 

입력 예시

 

5 17

 

출력 예시

 

2

 

 

---

 

풀이

 

경로 탐색 문제이지만, 시간에 따라 목적지인 동생의 위치가 바뀌므로 동생의 위치까지 고려하여 visited를 작성해야 한다.

 

그런데 한가지 팁이 있다. 수빈이는 -1, +1의 조합으로 2 시간단위마다 현재 위치로 다시 돌아올 수 있다. 따라서, 수빈이가 방문한 지점에서 (t + 2*n 시간) (n은 음이 아닌 정수) 이후에 수빈이의 동생이 같은 지점에 온다면, 그 시점에 수빈이는 동생을 반드시 잡을 수 있다.

 

따라서 visited에는 1. 최초 도착 시간 2. 도착 시간의 홀수 짝수 여부 모두가 저장되어야 한다. 이를 토대로 경로 탐색을 시행한 후, 수빈이 동생의 시간에 따른 방문 좌표를 visited를 통해 검사할 수 있다. 만약 둘의 홀짝 여부가 일치하고, 수빈이 동생의 시간보다 visited에 저장된 시간이 작거나 같다면 정답 후보를 얻을 수 있는 셈이다.

 

풀이 코드

from collections import deque
MAX = 500001

N, K = map(int, input().split())
answer_list = [K]
t = 1
while answer_list[-1] < MAX :
  answer_list.append(answer_list[-1] + t)
  t += 1

q = deque([(N, 0)])
visited = [[MAX]*MAX for _ in range(2)]
visited[0][N] = 0
answer = MAX
while q :
  now, t = q.popleft()
  for nxt in [now*2, now-1, now+1] :
    if -1 < nxt < MAX and visited[(t+1)%2][nxt] > t+1 and answer_list[t+1] < MAX :
      visited[(t+1)%2][nxt] = t + 1
      q.append((nxt, t+1))

for t, now in enumerate(answer_list[:-1]) :
  if visited[t%2][now] <= t :
    answer = min(answer, t)
print(answer if answer < MAX else -1)

풀이 완료!