[백준 17071] 숨바꼭질 5 [Java]

문제

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

---

풀이

수빈이와 동생이 각각 N, K에서 이동할 때 몇 초 후에 서로 만날 수 있는지 계산하는 문제다.

수빈이는 다음과 같이 움직일 수 있다.

• X - 1
• X + 1
• 2X

동생은 다음과 같이 움직일 수 있다.

• N + K

K는 경과 시간이자. 동생이 움직일 수 있는 거리를 의미한다. 풀이에서는 step으로 표현하겠다.

만약 N == K인 경우 수빈이와 동생은 제자리에서 만나므로 탐색이 불필요하다. 걸린 시간은 0초다.

bfs로 N부터 탐색을 시작하자.

큐가 비어있거나, k(동생의 이동 위치)가 500,000이하라면 탐색을 계속해야 하므로 동생의 이동거리부터 계산하며 조건식에 포함시켜주자.

본격적으로 풀이를 하기전에 시간복잡도에 대해 생각해보자.

수빈이는 X - 1, X + 1, 2X 총 3가지의 이동이 가능하다. 이 중 X - 1, X + 1은 무수히 많은 탐색 지점을 생성할 것이다.

ex) 50 👉 49, 51 -> 48, 50, 50, 51 👉 47, 49, 49, 51, 49, 51, 50, 52 👉 ...

따라서 탐색 여부를 표시해( visited[next] ) 중복 탐색을 방지해야 하지만, 수빈이와 동생 둘 다 이동하므로 탐색 종료 조건이 매번 달라진다. 무조건 중복을 방지하면 올바른 결과가 나오지 않는다.

그러면 이를 어떻게 해결할 수 있을까?

 

홀짝을 사용해 1초 전과 2초 전의 상태( step % 2 )로 구분하면 된다.

이 문제의 핵심 아이디어다.

수빈이의 이동(1씩 증감)에 따른 정점은 현재 시간(step)의 홀짝 여부에 따라 다른 배열에 기록되므로, 중복 탐색을 방지하면서도, 변하는 탐색 종료 조건에 대해 모든 경우의 수를 살펴볼 수 있다.

현재 큐에 기록된 수빈이의 위치들에 대해 이동 가능한 수를( curStepQueueSize ) 새로 큐에 삽입해줘야 한다.

큐를 새로 할당받아도 되지만, 현재 큐의 크기만큼 요소를 뽑아내어 새로운 경우의 수만 저장할 수 있다.

수빈이와 동생은 0 ≤ N, K ≤ 500,000만큼만 이동 가능하므로 범위를 벗어나는 수는 무시하고, 방문 여부를 확인 후 다음 탐색 지점을 큐에 등록하자.

이때, 수빈이의 다음 지점이 동생이 있는 곳과 일치한다면(next == k) 탐색을 중단하고 현재 시간을 반환하면 된다.

이제 수빈이와 동생은 동일한 시간 내 이동을 마쳤다. 

다시 동생이 이동한 경우를 살펴보자.

예를 들어 2초전에 수빈이가 10번 위치를 방문했다면, X - 1, X + 1에 따라 현재 다시 10번 위치를 방문할 수 있다.

이는 step의 홀짝에 따라 visited에 기록되며 따로 탐색할 필요는 없지만, 모든 경우의 수를 고려할 수 있게 해준다.

---

소스코드

보기