数据检验

격자의 각 면을 정점으로 하는 듀얼 그래프 $D$를 만든다. 내부 면은 $(N-1)(M-1)$개이며, 격자 바깥 전체를 하나의 외부 면으로 본다.

원래 그래프의 유향 간선 $e$를 진행 방향으로 바라보았을 때 오른쪽 면을 $R(e)$, 왼쪽 면을 $L(e)$라 하자. 듀얼 그래프에는 다음 간선을 추가한다.

$$R(e) \to L(e)$$

이제 $D$의 강한 연결 요소를 구하고, 축약 그래프를 생각한다.

보조정리 1. 원래 그래프의 유향 사이클 안쪽에는 외부 면을 포함하지 않는 source SCC 또는 sink SCC가 존재한다.

유향 사이클이 시계 방향이면 사이클 안쪽은 모든 간선의 오른쪽에 있다. 따라서 사이클을 가로지르는 듀얼 간선은 안쪽에서 바깥쪽으로만 향한다. 사이클 안쪽 SCC들 중 source를 하나 고르면, 이는 전체 축약 그래프에서도 source이다.

유향 사이클이 반시계 방향이면 같은 논리로 듀얼 간선이 바깥쪽에서 안쪽으로만 향한다. 사이클 안쪽 SCC들 중 sink를 하나 고르면 된다.

보조정리 2. 외부 면을 포함하지 않는 source SCC 또는 sink SCC의 면들을 둘러싸는 바깥 경계에는 유향 사이클이 존재한다.

source SCC에는 다른 SCC에서 들어오는 듀얼 간선이 없다. 따라서 경계를 가로지르는 모든 듀얼 간선의 방향이 SCC의 안쪽에서 바깥쪽으로 일정하다. 듀얼 간선을 오른쪽 면에서 왼쪽 면으로 정의했으므로, 원래 그래프에서 이 경계는 한 방향으로 이어지는 유향 사이클이다. sink SCC도 방향만 반대이고 동일하다.

SCC에 속한 내부 면의 행 범위가 $a$부터 $b$, 열 범위가 $c$부터 $d$라 하자. 그 SCC의 바깥 경계를 포함하는 최소 정점 직사각형은

$$(a+1,c+1,b+2,d+2)$$

이다. 이 직사각형의 넓이는 $(b-a+2)(d-c+2)$이다.

보조정리 2에 의해 각 후보 직사각형은 실제로 유향 사이클을 포함한다. 반대로 임의의 유향 사이클에 보조정리 1을 적용하면, 그 사이클의 직사각형 안에 들어가는 후보 SCC를 얻는다. 따라서 외부 면 SCC를 제외한 source SCC와 sink SCC의 경계 직사각형만 비교하면 최적해를 얻는다.

면의 수가 최대 약 $2.5 \cdot 10^7$이므로 일반적인 인접 리스트는 메모리를 많이 사용한다. 각 내부 면의 네 이웃은 $H,V$에서 즉시 계산할 수 있다. 외부 면에 인접한 간선만 별도 배열에 저장한 뒤, 암시적 그래프에서 반복형 Kosaraju 알고리즘을 수행한다.

시간 복잡도는 $O(NM)$이고, 메모리 복잡도는 $O(NM)$이다.

Solution written by GPT5.6