문제 74
트랜스포머 나이트
크기가 $N\times M$인 격자판의 맨 왼쪽 위 칸에 트랜스포머 나이트가 하나 놓여 있다. 트랜스포머 나이트는 체스 나이트 또는 퍼즈(Ferz)처럼 이동할 수 있다.
- 나이트는 현재 자신이 있는 칸에서 가로로 $2$칸, 세로로 $1$칸 떨어진 칸으로 이동하거나 가로로 $1$칸, 세로로 $2$칸 떨어진 칸으로 이동할 수 있다.
- 퍼즈는 현재 자신이 있는 칸에서 가로로 $1$칸, 세로로 $1$칸 떨어진 칸으로 이동할 수 있다.
첫 번째 이동에는 나이트의 이동 방식을 사용하며, 이후 나이트와 퍼즈의 이동 방식을 번갈아 가며 사용한다.
트랜스포머 나이트를 격자판의 맨 오른쪽 아래 칸에 놓기 위한 이동 횟수의 최솟값을 구하는 프로그램을 작성하라.
입력
첫 번째 줄에 두 정수 $N$, $M$이 공백으로 구분되어 주어진다. $(3 \le N, M \le 1\,000)$
출력
첫 번째 줄에 트랜스포머 나이트를 맨 오른쪽 아래 칸으로 옮기는 데 필요한 이동 횟수의 최솟값을 출력한다.
예제 입력 1
8 8
예제 출력 1
7
예제 입력 2
3 5
예제 출력 2
3
공식 해설
같은 칸에 도착했더라도 다음에 나이트로 움직일지 퍼즈로 움직일지에 따라 이후 이동이 달라진다. 따라서 방문 여부를 칸만으로 구분하면 안 된다.
현재 행, 열, 다음 이동 종류를 하나의 상태로 둔다. 시작 상태는 맨 왼쪽 위 칸이며 다음 이동 종류는 나이트이다. 현재 종류에 맞는 이동 중 격자 안에 도착하는 이동만 시도하고, 다음 상태에서는 이동 종류를 바꾼다.
상태 사이의 이동은 모두 한 번의 이동에 해당하므로 BFS로 최소 횟수를 구한다. 각 상태에 처음 도착했을 때 방문 표시를 하여 중복으로 큐에 넣지 않는다. 목적지의 두 상태 중 더 짧은 거리를 답으로 택하거나, BFS에서 목적지를 처음 꺼냈을 때 종료해도 된다.
상태는 $2NM$개이고 상태당 가능한 이동 수는 상수이므로 시간복잡도와 공간복잡도는 $O(NM)$이다.
구현 · 언어별 풀이
C++ 구현
거리는 칸마다 다음 이동 종류 두 개를 저장하도록 만들고 $-1$로 초기화한다. 큐에는 행·열·종류를 함께 넣는다. 목적지의 두 거리 중 $-1$은 도달하지 못한 상태이므로 제외하고 최솟값을 구한다.
C 구현
종류와 칸 번호를 합쳐 상태 번호를 만들고 2*N*M칸의 int 거리 배열을 둔다. 큐에도 상태 번호만 저장하면 된다. 방문 표시는 넣을 때 하며 다음 종류의 이동 규칙으로 이웃을 만든다.
Python 구현
거리 배열은 array('i')로 평탄화하고 deque에는 인코딩한 상태 번호를 넣는다. (행,열)만 방문 처리하면 종류가 다른 상태를 잘못 합친다. 큐에 넣을 때 거리와 종류를 함께 확정한다.
Java 구현
int[] dist와 int 배열 큐에 종류를 포함한 상태 번호를 저장한다. 최대 2000000 상태라 객체 튜플을 상태마다 만들 필요는 없다. 같은 칸의 두 종류는 서로 다른 거리 항목이다.
Rust 구현
Vec<i32> 거리와 VecDeque<usize> 상태 큐를 사용한다. 상태를 종류*(N*M)+행*M+열로 인코딩한다. 종류가 바뀐 도착 상태의 방문 여부를 검사한다.
JavaScript 구현
같은 칸이라도 다음 이동 방식이 다르면 다른 BFS 상태이다. 칸 번호를 $rM+c$라 할 때 상태를 2 * (r * m + c) + kind로 표현한다. kind=0은 다음에 나이트, $1$은 다음에 퍼즈로 이동할 상태로 정하면 시작 상태는 $0$이다.
나이트는 $(\pm1,\pm2)$와 $(\pm2,\pm1)$의 여덟 이동, 퍼즈는 $(\pm1,\pm1)$의 네 이동을 사용한다. 다음 상태의 방식은 1 - kind로 바꾼다. 같은 좌표를 서로 다른 방식으로 방문하는 것은 허용한다.
최대 상태 수는 $2NM\le2\cdot10^6$이다. 거리와 큐는 Int32Array로 두고 거리를 -1로 초기화한다. 발견한 순간 거리를 쓰고 큐에 넣으면 각 상태가 한 번만 들어가 큐 크기도 제한된다. 종료 칸의 두 방식 중 도달 가능한 최소 거리를 답으로 사용한다.