모두 $N \times M$ 사각 격자판에서 $(A, B)$에서 $(C, D)$로 가는 최장 경로가 방문하는 칸의 개수, 또는 최장 경로를 아무거나 하나 구하는 문제이다.

  • NMABCD
    • 테스트 케이스의 개수 $t \le 1600$
    • 입력 제한: $1 \le N, M \le 5000$, $2 \le NM \le 10^5$
    • 최장 경로가 방문하는 칸의 개수만 출력
  • 숫자 퍼즐
    • 테스트 케이스의 개수는 주어지지 않음
    • 입력 제한: $2 \le N, M \le 100$, $N, M$은 짝수
    • 해밀턴 경로가 존재할 경우에만 경로를 출력
  • Grid travel
    • 테스트 케이스의 개수는 주어지지 않음
    • 입력 제한: $2 \le N, M \le 100$
    • 최장 경로를 출력

일단, 최장 경로 문제는 격자 그래프에서도 NP-complete이다. 하지만 완전한 직사각형 그래프로 한정하면 P라는 내용의 2012년 논문이 있다. 테스트 케이스의 개수가 많고 직사각형의 크기도 매우 크므로, 경우를 나누어 경로를 직접 찾지 않고 답을 구해야 함을 추측할 수 있다.

일반성을 잃지 않고 $N \le M$이라고 하자. 아니라면 가로와 세로를 뒤집어서 구하면 된다. 편의상 “경로의 길이"를 경로상의 칸의 개수라는 의미로 사용한다.

Parity argument

먼저 시작점과 끝점의 parity를 이용하여 경로의 길이의 상한을 구할 수 있다. 맨 왼쪽 위 칸을 검은색으로 하는 체스판을 상상해 보자.

  • $NM$이 짝수인 경우: 시작점과 끝점의 색이 다르면 $NM$, 같으면 $NM-1$
  • $NM$이 홀수인 경우: 이 경우는 검은색이 흰색보다 한 칸 많다.
    • 시작점과 끝점이 모두 검은색이면 $NM$
    • 시작점과 끝점의 색이 다르면 $NM-1$
    • 시작점과 끝점이 모두 흰색이면 $NM-2$

이 값을 parity max라고 하자.

$N = 1$인 경우

직사각형이 한 줄이므로, 왼쪽이나 오른쪽으로만 이동할 수 있다. $B < D$를 가정하면 오른쪽으로만 가야 끝점에 도착할 수 있다. 이때 길이는 $D - B + 1$이다.

$N = 2$인 경우

역시 $B \le D$를 가정한다.

  • $B = D$이거나 $B + 1 = D$이고 $A \neq C$이면, 시작점과 끝점이 전체 직사각형을 왼쪽과 오른쪽의 두 영역으로 나눈다. 맨 왼쪽 열을 포함하는 C자 경로와 맨 오른쪽 열을 포함하는 C자 경로 중 하나를 선택할 수 있고, 그 둘 중 긴 것을 출력하면 된다.
  • 아니라면, 시작점 $(A, B)$에서 시작하여 왼쪽으로 돈 다음 $(A’, B)$를 통해서 오른쪽으로 나올 수 있다. ($A’$는 $A$의 반대쪽 행) 끝점 쪽의 경로도 똑같이 그려놓으면 $N = 2$의 더 작은 직사각형에서 맨 왼쪽 열의 한 꼭짓점과 맨 오른쪽 열의 한 꼭짓점을 연결하는 문제가 된다. 나머지 칸을 ㄹ자로 이으면 $(A, B)$와 $(C, D)$의 parity가 다를 때는 모든 칸을 밟을 수 있고, 같을 때는 한 칸을 빼고 모두 밟을 수 있다. 따라서 이 경우의 답은 parity max가 된다.

$N = 3$인 경우

가장 복잡하고, 이 경우에서만 3번 틀렸다.

여기서부터 판을 압축하는 아이디어를 본격적으로 사용한다.

시작점의 왼쪽 또는 끝점의 오른쪽에 2개 이상의 열이 있다면, 열을 2개 제거한 경우의 답을 찾아서 끝 열에서의 세로 방향 이동을 다음과 같은 방법으로 확장할 수 있다.

N=3에서 가로를 두 칸씩 확장하는 방법 (1)

N=3에서 가로를 두 칸씩 확장하는 방법 (1)

시작점과 끝점이 서로 다른 열에 있고 그 사이에 2개 이상의 열이 있는 경우에도 비슷하게 확장이 된다. 왼쪽에서 오른쪽으로 가려면 한 번 또는 세 번 가로지를 수 있으므로 아래의 그림의 경우가 모든 경우가 된다. 가운데 행만을 통해서 지나가는 곳은 확장할 수 없으나, 두 점 사이에 열이 적어도 하나 있는 경우(즉, $B + 1 < D$)에 가운데 행만으로 두 번 지나가는 것은 최적이 아닐 것임을 어렵지 않게 예상할 수 있으므로, 사이에 열이 하나 또는 2개 남을 때까지 줄일 수 있다.

N=3에서 가로를 두 칸씩 확장하는 방법 (2)

N=3에서 가로를 두 칸씩 확장하는 방법 (2)

이제 남은 모든 경우에 대해 백트래킹을 짜서 결과를 확인해보면 된다. 대부분의 경우에서 parity max만큼을 밟을 수 있기 때문에, 그만큼 밟지 못하는 경우만 추리면 다음의 조건을 모두 만족하는 경우가 된다.

  • $M$이 짝수이다.
  • $B \neq D$이고. $B < D$를 가정하면, $(A, B)$는 흰색이고 $(C, D)$는 검은색이다.
  • $A$가 1이나 3일 경우, $B + 1 = D$인 경우를 제외하여야 한다.

$N \ge 4$인 경우

같은 방식으로 판을 압축하여 $(N, M)$을 $(4, 4)$, $(4, 5)$, $(5, 5)$ 중 하나로 만들 수 있다. 각각 모든 시작점과 끝점에 대해 백트래킹을 해보면 모두 parity max가 최장 경로임을 알 수 있다.

여기까지의 결과를 이용하면 25461. NMABCD를 풀 수 있다.

실해 구성

9021. 숫자 퍼즐과 27693. Grid travel을 풀기 위해서는 실제로 최장 경로를 구성해야 하며, 그러려면 “확장 알고리즘"을 잘 구체화하여야 한다.

어떤 최장 경로의 중간에 2개의 세로줄을 새로 삽입하면, 그 사이를 가로지르는 선이 존재할 수 있고, 바로 왼쪽이나 오른쪽 세로줄을 세로로 지나가는 선이 존재할 수 있다. 각각의 존재 여부에 따라 몇 가지 방법으로 2개의 세로줄의 모든 칸을 밟는 경로를 삽입할 수 있고, 본인의 코드에서 구현한 방법은 다음과 같다.

N≥4에서 가로를 두 칸씩 확장하는 방법

N≥4에서 가로를 두 칸씩 확장하는 방법

하나의 가로선은 U자로 구부려서 그 위쪽이나 아래쪽의 공간을 하나 채울 수 있다. 하나의 가로선이 맨 위 가로줄을 지나간다면 모든 가로선을 아래로 구부려서 모든 칸을 채울 수 있다. 두 개의 가로선이 서로 이웃하다면 그 경계를 기준으로 위쪽 가로선은 위로, 아래쪽 가로선은 아래로 구부리면 된다. 두 개의 가로선 사이에 두 줄 이상의 공간이 있고 그 옆에 세로선이 하나 지나간다면, 그 세로선을 확장시켜서 중간의 공간을 한 바퀴 돌아 나올 수 있고, 나머지 공간은 같은 방법으로 채울 수 있다.

테두리 쪽에 줄을 삽입하는 경우에는 그 옆을 지나가는 세로선이 반드시 존재하므로 그 선을 확장해서 공간을 채우면 된다.

하지만 확장이 불가능한 경우가 아예 없는 것은 아니기 때문에, $N, M \le 11$ 범위에서 모든 가능한 입력을 넣어보고 모두 NMABCD의 답 만큼의 길이의 출력이 나오는 것을 확인하고 나서 제출하는 것이 좋다. 만에 하나 그런 경우가 생긴다면 백트래킹에서 시도하는 방향의 순서를 바꿔주면 해결될 것이다.