BOJ 29984 Onix

이 문제는 경로를 관리하는 커넥션 프로파일 DP로 풀 수 있습니다.

임의의 경로를 하나 잡고, 사각 격자 전체를 다음의 모양으로 잘랐다고 가정해 봅시다.

이렇게 잘랐을 때 경계선의 칸 수는 $n+1$칸(그림의 ?의 개수)이고, 이러한 $n+1$칸 각각에 대해 경로가 그 칸을 통과할 수도 있고, 통과하지 않을 수도 있습니다. 맨 왼쪽 위 칸에서 시작하여 맨 왼쪽 아래 칸에서 끝나는 경로를 이렇게 자르면, 경로의 부분들 중에서 그림에 표시된 영역에 포함되는 것은 맨 왼쪽 위 칸에서 시작해서 끊어진 경로 하나가 있고, 추가로 양 끝이 끊어진 부분 경로가 0개 이상이 있게 됩니다.

이제 각 경계선의 상태를 적절한 방법으로 나타낼 것입니다. 이를 위해, 왼쪽 변에서 시작하여 경계선을 따라 경계선의 각 칸에 1부터 $n+1$까지 순서대로 번호를 붙입니다. 그리고 다음의 방법으로 길이 $n+1$의 배열 $a_1, a_2, \cdots, a_{n+1}$을 만들 수 있습니다.

• 맨 왼쪽 위 칸에 연결된 경로가 지나가는 경계 $i$에 대해서, $a_i = i$로 둡니다.
• 경계 $i$를 통해 들어간 부분 경로가 경계 $j$를 통해 나오거나 그 반대라면, $a_i = j, a_j = i$로 둡니다.
• 나머지 경계는 $a_i = 0$으로 둡니다.

예를 들어, 다음의 경우에 이 배열은 [0, 0, 3, 0, 6, 5]가 됩니다.

이제 전이를 설계해야 합니다. 전이는 다음의 그림과 같이 한 칸 단위로, 왼쪽에서 $i$번째 칸을 처리할 때 $a_i$와 $a_{i+1}$, 그리고 이들과 연결된 경로의 끝점들의 상태를 업데이트하는 방식으로 진행됩니다.

이 문제의 경우, 구체적으로 다음의 과정을 통해 전이를 할 수 있습니다.

• $a_i \ne 0$, $a_{i+1} \ne 0$인 경우
  • 둘 모두 어떤 경로의 끝점이므로 둘을 서로 연결해야 합니다. 그 결과 $a_i' = a_{i+1}' = 0$이 됩니다.
  • $a_i = i$였다면 $i+1$과 연결된 경로의 반대쪽 끝점, 즉 $a_{a_{i+1}}$을 $a_{i+1}$로 수정하여 출발점에서 연결된 경로임을 표시해 줍니다.
  • $a_{i+1} = i+1$이었다면 마찬가지로 처리합니다.
  • $a_i = i+1, a_{i+1} = i$였다면 둘을 연결하면 닫힌 루프가 만들어지므로 전이하지 않습니다.
  • 그렇지 않은 경우, $i$의 반대쪽과 $i+1$의 반대쪽을 서로 연결해 줍니다.
• $a_i = 0$인 경우
  • $i+1$에서 연결된 부분 경로는 $i'$로 나가거나 $i+1'$로 나갈 수 있습니다.
  • 두 가지 가능성에 대해 적절히 처리해 주고, $i+1$의 반대쪽도 (존재한다면) 업데이트해 줍니다.
• $a_{i+1} = 0$인 경우도 마찬가지로 구현해 줍니다.
• 둘 다 0인 경우
  • 이 경우에는 새로 생기는 두 경계를 잇는 새로운 경로를 만들어야 합니다.
  • $a_{i} = i+1$, $a_{i+1} = i$로 만들어주면 됩니다.

한 칸씩 처리하여 한 줄의 끝에 도달했다면, 현재의 경계는 ___| 모양일 것입니다. 여기서 다음 줄로 넘어갈 때는 |¯¯¯ 모양으로 만들어야 하는데, 다음과 같이 처리해 주면 됩니다.

• 맨 마지막 칸을 통과하는 경로가 있다면 무시합니다.
• 그렇지 않다면, 나머지 칸의 값들을 한 칸씩 오른쪽으로 밀고, 0이 아닌 모든 값들에 1을 더해주면 모든 연결성이 유지됩니다.

맨 왼쪽 위 칸에서 시작하여 맨 왼쪽 아래 칸에서 끝나는 경로는, 맨 왼쪽 위 칸의 바로 위에서 시작하여 맨 왼쪽 아래 칸의 바로 아래에서 끝나는 것으로도 볼 수 있으므로, 시작 상태와 끝 상태를 모두 $a_2 = 2, a_i (i \ne 2) = 0$으로 둡니다.

마지막으로 DP 테이블을 해시맵으로 만들어서 각 상태의 경우의 수를 저장해 주면 시간 내에 충분히 통과할 수 있습니다. 잘 구현했다면 파이썬으로 $n = 11$까지도 수 초 내에 구해집니다.