BOJ 17970 Islands

https://acmicpc.net/problem/17970

문제의 재구성

일반성을 잃지 않고, 첫 번째 섬에는 1 2 ... N이 차례로 쓰여 있다고 가정하겠습니다. 그냥 그에 맞춰서 두 번째 섬에 번호를 다시 붙여 주면 됩니다.

문제를 이렇게 재구성할 수 있습니다. 편의상 모든 수는 mod N을 취한다고 하겠습니다. 예를 들어 0은 N과 같습니다. "순열이 주어진다. 한 점을 골라 시작해서, 한 번에 한 칸씩 옆으로 확장을 해야 한다. 단, k가 적힌 칸으로 확장을 하려면 k-1 또는 k+1이 적힌 칸이 이미 확장된 상태여야 한다."

시작점 하나를 임의로 잡고 확장이 가능한 대로 바로 확장해 주면 됩니다. 즉 왼쪽으로 확장할 수 있으면 왼쪽으로 확장하고, 오른쪽으로 확장할 수 있으면 오른쪽으로 확장합니다. 양쪽으로 모두 확장할 수 있으면 어느 쪽이든 먼저 해도 됩니다.

왼쪽에서 오른쪽으로, 모든 점에 대해, 각 점을 시작점으로 두고 확장을 시뮬레이션하면 답을 얻어낼 수 있습니다. 하지만 이렇게 하면 O(N^2)이 됩니다.

최적화?

불필요한 시작점을 건너뛰어 봅시다.

보조정리. x가 시작점일 때 모든 점으로 확장할 수 없다고 해봅시다. (이를 "실패"라고 합시다.) 이때 x가 시작점일 때 y로 확장할 수 있다면, y가 시작점일 때에도 실패합니다. 

증명. y가 시작점일 때 성공한다고 가정합시다. 그러면 y가 시작점일 때 확장되지만 x가 시작점일 때 확장되지 않는 점이 존재합니다. 그 중에서 가장 먼저 확장되는 점을 z라고 합시다.

y가 시작점일 때 z로 확장되기 전까지 확장된 점의 집합을 Y라고 두고, x가 시작점일 때 확장되는 모든 점의 집합을 X라고 하면, Y는 X의 부분집합입니다. 따라서 X에서도 z로 확장이 가능해야 하고, 이는 모순입니다.

그러므로 확장에 실패했다면, 방금까지 확장에 성공한 점들을 다 건너뛰고 그 다음 점을 시작점으로 잡으면 됩니다. 하지만 이런다고 한들 시간 복잡도 상으로 의미가 있을까요? 이게 자명하지 않은 이유는 한 칸이 서로 다른 시작점에서부터 여러 번 확장될 수 있기 때문입니다.

최적화!

놀랍게도 의미가 있습니다! 이 알고리즘은 이제 O(N)에 동작합니다.

정리. 모든 점은 최대 세 번 확장됩니다. 

증명. 아래 참조

일단 첫 번째 점을 시작점으로 두고 확장을 시뮬레이션해 봅시다. 아래 그림에서 색칠된 칸은 확장된 칸을 나타냅니다.

시작점의 후보를 왼쪽에서 오른쪽으로 보고 있으므로, 이제부터의 모든 확장은 흰 색 구간의 왼쪽 부분을 덮게 됩니다. 따라서 확장된 칸의 상태는 항상 위의 꼴로 나타내어집니다.

이미 확장된 칸 A를 하나 잡습니다. 예를 들어 두 번째 칸을 잡읍시다. 이후의 어떤 확장이 그 칸을 덮게 된다면, 그 후에는 최대 한 번만 그 칸이 덮일 것임을 증명하겠습니다. 아래 그림에서 S는 확장을 시작한 칸입니다.

만약 S에서 시작한 확장이 흰색 칸 전체를 덮어서 오른쪽 회색 칸까지 확장된다면, 더 이상 시작점을 보지 않아도 됩니다. 모든 칸이 방문된 상태이기 때문입니다. 그렇지 않고 흰색 칸이 남는다고 가정합시다. S에서 시작해서 확장된 맨 오른쪽 칸을 B라고 둡시다.

회색 칸에 적힌 수는 하나의 구간을 이룹니다. 이를 [L, R]이라고 합시다.

회색 구간은 한 방향으로만 확장할 수 있으므로, A부터 S-1까지는 연속된 수를 이룹니다. 즉 순서대로 L+k, L+k-1, ..., L이거나, R-k, R-k+1, ..., R입니다. 일반성을 잃지 않고 후자라고 합시다. 그러면 S는 R+1보다 커야 하고, S+1, S+2, ..., B 중 하나가 R+1이어야 합니다.

그런데 이러면 A, A+1, ..., S, S+1, ...이 연속된 수를 이루지 않습니다. 따라서 S 이후의 시작점에서 확장을 시작하고 A까지 가려면, 오른쪽으로 쭉 가서 흰색 칸 전체를 덮어야 합니다. 따라서 S 이후에는 A가 최대 한 번 방문됩니다.