[BOJ 33961] 체스평평설
- 문제풀이
문제
찬우는 더 이상 지구나 나무 같은 따분한 것을 평평하게 만들기에 지쳤다. 대신 체스의 아름다움에 푹 매료되어 체스판을 평평하게 만들기로 결심했다!
"잠깐 wait! 체스판은 원래 평평한거 아닌가요?"
날카로운 지적이다. 하지만 의심이 많은 찬우는 굳이 체스판이 평평한지 직접 확인을 해보려고 한다. 먼저, 찬우는 나숍(Knishop)이라는 기물을 준비했다. 나숍(Knishop)은 체스에서 나이트외 비숍의 특징을 합친 기물로, $2 \times 1$만큼 대각선으로 이동하거나 대각선 방향으로 원하는 만큼 이동할 수 있다.
체스판에서 나숍이 이동할 수 있는 곳
이제 찬우는 준비한 나숍을 체스판의 임의의 위치에 두고, 해당 위치를 시작으로 모든 체스판의 칸을 정확히 1번씩만 들르는 Knishop-tour를 할 것이다. 모든 칸을 들르면서 각 칸의 높이가 일정한지 확인하는 것으로 찬우는 체스평평설을 자신있게 지지할 수 있게 될 것이다.
마침 찬우는 동방에서 체스평평설의 좋은 근거가 되어줄 수 있는 $2 \times M$ 모양의 체스판을 발견했지만, 정작 어떤 순서로 Knishop-tour를 돌아야 할지 몰라 곤경에 처했다. 찬우를 도와 Knishop-tour 경로를 대신 만들어주자!
입력
첫 번째 줄에 체스판의 크기를 나타내는 $M$이 주어진다. 이는 체스판이 $2 \times M$ 모양임을 의미한다. $(1 \le M \le 10000)$
출력
주어진 체스판에서 Knishop-tour가 가능하다면 첫 번째 줄에 YES를 출력한다.
이후 $2 \times M$개의 줄에서는 Knishop-tour의 경로를 차례대로 출력한다. 각 $i$번째 줄에는 Knishop-tour의 $i$번째 보드칸의 위치 $(x_i,y_i)$를 공백으로 구분하여 출력해야 하며, $1 \le x_i \le 2, 1 \le y_i \le M$을 만족해야 한다.
이때 경로의 시작 및 끝 좌표는 아무 곳에서 시작할 수 있고, 아무 곳에서 끝날 수 있다. 문제의 조건을 만족하는 경로가 여러가지일 경우 아무거나 출력해도 된다.
Knishop-tour가 불가능하다면 첫 번째 줄에 NO를 출력한다.
제한
| 시간 제한 | 메모리 제한 |
|---|---|
| 1sec | 1024MB |
풀이
$2 \times M$ 크기의 체스판에서 ‘나숍(Knishop)’ 기물을 이용하여 모든 칸을 정확히 한 번씩 방문하는 경로를 찾는 문제다. 나숍은 나이트의 이동($2 \times 1$ 대각선)과 비숍의 이동(임의 거리 대각선)을 모두 수행할 수 있는 특수한 기물이다. 체스판의 가로 길이 $M$이 $1$ 또는 $2$인 경우에는 기물의 이동 특성상 모든 칸을 방문하는 것이 불가능하므로 NO를 출력한다.
$M \ge 3$인 경우에 대해서는 체스판을 일정한 단위 블록으로 나누어 경로를 구성하는 해 구성하기(Constructive) 전략을 사용한다. 구체적으로 $2 \times 3$, $2 \times 4$, $2 \times 5$ 크기의 소형 체스판에서 모든 칸을 방문하는 기본 패턴을 미리 정의한다. 시작점을 (1, 1)로 두었을 때, 도착점이 (2, n)이라면 대각선 이동을 통해 다음 시작점인 (1, 1)로 이동할 수 있음이 보장되기 때문에, 해를 구성할 때 가능하면 도착점을 우하단에 맞추는 것을 고려한다. 아래는 그 예시이다.
그리고, 임의의 $M \ge 3$은 다음과 같은 수식으로 분해할 수 있다:
\[M = 3a + 4b\]단, $M=5$인 경우는 위 수식으로 분해되지 않으므로 예외적으로 별도의 패턴을 적용한다. $M \ge 6$인 모든 정수는 $3$과 $4$의 합으로 표현 가능하므로, 앞서 정의한 $2 \times 3$ 패턴과 $2 \times 4$ 패턴을 적절히 조합하여 전체 경로를 완성한다.
이 알고리즘은 $M$의 크기에 비례하여 경로를 출력하므로 시간 복잡도는 다음과 같다:
\[O(M)\]$M$이 최대 $10\,000$이므로 제한 시간 $1$초 내에 효율적으로 해결 가능하다.
소스코드
Github Link : Source Code
참고 알고리즘 :