백준 1783 병든 나이트 문제 풀이
백준 온라인 저지, 1783번: 병든 나이트
도입
병든 나이트는 세로 축 상에서는 위 아래로 이동하여 이전의 좌표로 복귀할 수 있으나, 가로 축 상에서는 항상 오른쪽으로 이동하므로 이전의 좌표로 복귀할 수 없다. 따라서 최대한 많은 가로 축 상 이동 횟수를 획득하는 것으로, 병든 나이트가 여행에서 방문할 수 있는 칸의 최대 개수를 구할 수 있다.
문제 풀이
세로 축 상 진동하여 이동
체스판의 세로 길이가 3 이상인 경우, 병든 나이프는 “1. 2칸 위로, 1칸 오른쪽”, “4. 2칸 아래로, 1칸 오른쪽”을 반복하여 행동하는 것으로 세로 방향으로 진동하여 움직일 수 있다.
이와 같이 진동하여 이동하면 매 움직임마다 오른쪽 방향으로 1칸씩 전진하므로, 최대한 많은 가로 축 상 이동 횟수를 획득할 수 있다.
다만 이동 횟수가 4회 이상인 경우에는 모든 이동 방법을 최소 한 번 사용해야 한다. 예제 입력 1을 예로 들면 오른쪽 방향으로 2칸 이동하는 2번 이동 방법과 3번 이동 방법을 각 1회 사용하고, 나머지 가로 축 상 여유 공간을 1번 이동 방법과 4번 이동 방법을 반복하는 것으로 총 48칸을 방문할 수 있다.
위와 같이 세로 축 상 진동 이동이 가능하다면 병든 나이트가 방문할 수 있는 칸의 개수의 최대값은 가로 길이 $M$에 대하여 $M - 2$이다.
세로 축 상 진동이 불가능하거나 체스 판의 가로 길이가 충분히 작은 경우
만약 세로 길이가 3 이하여서 병든 나이트가 세로 축 상 진동 이동을 할 수 없는 경우, 1번 이동 방법과 4번 이동 방법을 사용하지 못하므로 병든 나이트는 4회 이상 이동할 수 없다.
만약 체스 판의 가로 길이가 충분히 작다면, “세로 축 상 이동을 3회 하는 것”이 위의 <세로 축 상 진동하여 이동> 전략보다 더 많은 칸을 방문할 수도 있다.
따라서 병든 나이트가 방문할 수 있는 칸의 개수의 최대값은 항상 $M - 2$인 것은 아니다.
하지만 이와 같은 경우, 병든 나이트는 4회 이상 이동할 수 없다. 3회의 이동 기회 상에서 병든 나이트가 할 수 있는 모든 행동의 가짓수는 $4 ^ 3 = 64$이므로, 모든 경우의 수를 완전탐색할 수 있다.
따라서 우선 병든 나이트가 4회 이상 이동할 수 없는 상황에 대해 완전탐색을 수행한 후, 체스판의 세로 길이가 3 이상인 경우에 <세로 축 상 진동하여 이동>의 결과 $M - 2$와 완전탐색의 결과 중 더 큰 값을 정답으로 제시한다.