링크

문제 요약

연못에 같은 크기의 정사각형 연잎이 서로 겹치지 않게 놓여있다. 개구리는 (0,0) 이 왼쪽 하단인 연잎에 존재하고, 해당 연잎으로부터 가로 혹은 세로로 최대 거리 d 만큼 뛸 수 있다. 이때, 개구리가 (0,0) 에서 가장 멀리 이동할 때 최대 거리를 구하는 문제이다. 이때 거리는 맨해튼 거리를 사용한다.

관찰

문제에서 요구하는 바를 잘 생각해보자. 문제에서 연잎 사이를 이동할 때 굳이 최단 거리로 이동해야할 필요가 없음을 알 수 있다. 만약 가로 방향으로 연잎 A, B, C 가 순서대로 있을 때, A에서 B와 C가 닿는다면 B에서 C도 자명히 닿는다는 것을 관찰 할 수 있을 것이다. 그러므로 A와 B 사이에 간선을 만들고, B와 C 사이에 간선을 만들어 A, B, C가 같은 컴포넌트에 존재함을 표현할 수 있다.

즉, A에서 C로 바로 갈 수 있지만, 굳이 최단거리 이동은 불필요하므로 reachability 만 따지자는 것이다. 또한 위에서 관찰한 내용은 세로방향에 대하여도 자명히 성립한다. 따라서 임의의 연잎에 대하여 자신으로부터 가로 혹은 세로로 뛸 수 있는 영역 중에 최초로 만나는 연잎과만 간선을 연결해주면 충분하다.

풀이

어떤 정점이 같은 컴포넌트에 있는지를 효율적으로 표현하는 방법은 DSU를 이용하는 것이다. 이제 각 연잎에서 서로 근접한 연잎들 사이에 연결만 빠르게 하면 문제가 풀릴 것이다. 이 과정은 Sweeping을 이용하면 $O(N\log{N})$ 에 가능하다. 각 연잎을 x좌표순으로 정렬한 뒤 (x가 같으면 y를 기준으로 정렬), 새롭게 연잎이 추가될 때마다, 새로운 연잎 기준으로 위와 아래를 살펴보고 가장 가까운 연잎과 연결을 하면 된다. (당연히 x좌표와 y좌표를 뒤집어서 위의 과정을 한번 더 하면, 좌우로 연결이 될 것이다.)

그렇다면 가장 가까운 연잎은 어떻게 찾을까? 연잎이 추가될 때마다 set에 연잎의 왼쪽 하단 좌표의 y좌표 값을 넣고, 자신의 (y좌표+r) 보다 크면서 최소인 값과, (y좌표-r) 보다 작으면서 최대인 값에 해당하는 연잎의 번호를 찾는다. 이후 현재 연잎과 찾은 연잎의 거리가 d 이내라면 해당 쌍을 서로 DSU로 union 하면 된다. 이 과정은 좌표압축과 합세그를 이용해서 구현이 가능하며, set에 lower_bound를 이용해서도 구현이 가능하다. 어떤 방식을 택하여도 전체 시간 복잡도는 $O(N\log{N}+N\alpha{(N)})$ 이다.

추가적으로 DSU를 이용하여 union하는 과정에서 맨해튼 거리의 최댓값을 갱신하는 것은 어떤 정점을 최상위 부모로 결정하는 것으로 쉽게 해결이 가능하므로 자세한 설명은 생략하겠다.