백준/BFS

백준 17071번

Reenact 2022. 2. 14. 17:05

다른 숨바꼭질과 다르게 최단거리로만 풀 수가 없었다. 동생을 먼저 이동시켜놓고 그다음 수빈이의 위치를 이동시켰다. 이 때 동생이 위치할 수 있는 좌표 중에 수빈이가 도달할 수 있는 최단 거리가 더 커지면 절대 동생을 그 위치에서 잡을 수 없다. 또 동생이 t초 후에 어떤 좌표에 있을 때 수빈이가 그 지점에 t보다 작으면서 t의 홀짝이 같도록 도착할 수 있으면 그 위치에서 동생을 잡을 수 있다.(같은 위치에서 1 -1을 반복해서 이동하면 되니) 이런 식으로 수빈이가 각 지점에 도착하는 최단시간을 홀수와 짝수로 나눠서 고려하였다. 그러면 O(n)이 걸린다.

'백준 > BFS' 카테고리의 다른 글

백준 9328번  (0) 2022.03.01
백준 11967번  (0) 2022.03.01
백준 16933번  (0) 2022.02.14
백준 14442번  (0) 2022.02.14
백준 13913번  (0) 2022.02.14