KnightL on a Chessboard

사이트: HackerRank
난이도: 미디움
분류: Search

문제

직각 형태로 움직일 수 있는 체스말 knight를 이용하여 n x n 크기의 체스판에서 (0, 0)에서 (n-1, n-1)까지 이동하는 최단경로를 찾아서 반환하라.

예를 들어, n=5일 때 이동할 수 있는 경우의 수는 아래와 같다.

[
  [♞, 0, 0, 0, 0],
  [0, 4, 4, 2, 8],
  [0, 4, 2, 4, 4],
  [0, 2, 4, -1, -1],
  [0, 8, 4, -1, 1]
]

처음 문제를 접하고 이해하기가 꽤 어려웠는데, 해당 문제는 위와 같이 첫 이동한 위치에서 (n-1, n-1) 까지 이동할 경우에 소요되는 횟수를 기록하는 것이다.
체스의 나이트 이동 규칙에 따라 (0, n)과 (n, 0)은 첫 이동 위치가 될 수 없다.

1. 나의 풀이

해당문제는 유형자체가 익숙하지도 않고 문제가 잘 이해되지 않아서 풀이 법을 바로 찾아보았다.

2. 다른사람의 풀이

python 코드로 풀이하신 분이 계셔서 코드를 참조하여 javascript로 변환하였다.

해당 문제는 bfs(너비 우선 탐색)를 이용하여 최단경로를 찾는 알고리즘이라고 한다. 입력 값으로 주어지는 n의 크기도 5 <= n <=25이기 때문에 체스 판을 모두 탐색해도 충분할 거 같다는 생각이 들었다.

function bfs(n, i, j) {
  	// 방문한 곳을 기록하기 위한 이중 배열 생성
  	// n-1 까지 기록하는 것이라서 길이를 n으로 생성한다.
    const checkVisit = Array.from(
        new Array(n), 
        () => new Array(n).fill(0)
    );
  	// bfs 탐색을 위한 queue이다
  	// (0, 0) 좌표부터 시작하기 때문에 초기 값은 [0, 0] 으로 설정한다.
    const queue = [[0, 0]];
  	// 나이트가 이동할 수 있는 전 방향 좌표 값이다.
    const dx = [i, i, -i, -i, j, -j, j, -j];
    const dy = [j, -j, j, -j, i, i, -i, -i];
    
    while(queue.length) {
      	// bfs 탐색 진행
        const [px, py] = queue.shift();
        
      	// 현재 좌표에서 전 방향을 순회한다.
        for(let p = 0; p < 8; p++) {
            // 방향 이동 계산
            const nx = px + dx[p];
            const ny = py + dy[p];
            
            if (
              	// 계산된 nx와 ny가 체스판 안에 존재하고,
              	(0 <= nx && nx < n) && 
                (0 <= ny && ny < n) && 
              	// 방문하지 않았다면
                checkVisit[nx][ny] == 0
            ) {
              	// bfs 탐색을 위한 queue에 추가한다.
                queue.push([nx, ny]);
              	// 현재 까지 이동한 횟수 + 1을 저장한다.
                checkVisit[nx][ny] = checkVisit[px][py] + 1;
            }
        }
    }

    if (checkVisit[n - 1][n - 1] === 0) {
        // (n-1 ,n-1) 까지 도달하지 못했다면 유효하지 않으므로 -1 반환
        return -1;
    } else {
        // (n-1 ,n-1) 까지 도달했다면 이동 횟수 반환
        return checkVisit[n - 1][n - 1];
    }
}

function knightlOnAChessboard(n) {
    // 나이트의 이동 규칙은 수직, 수평으로 이동했다가 마지막에 한칸 옆으로 이동하게 된다.
  	// 그렇기 때문에 첫줄((0, n)과 (n, 0)을 뜻한다)은 첫번째 출발점으로 기록할 필요가 없다.
  	// 따라서 n-1의 길이를 가지는 이중 배열을 생성한다.
    const result = Array.from(
        new Array(n - 1), 
        () => new Array(n - 1).fill(0)
    );
    
  	// 나이트 이동 패턴과 체스판의 규칙으로 인해 절반만 구하면 된다.
    for (let i = 1; i < n; i++) {
        for (let j = i; j < n; j++) {
          	// 첫 이동한 경로가 나이트가 이동할 수 있는 규칙이 되어 전달된다.
            // 예를 들어 (1, 1)일 경우 아래로 한 칸 움직이고 옆으로 한 칸 움직이는 패턴을 가지는 것이다.
            const value = bfs(n, i, j);
          	// 값을 구했다면 반대편 위치에도 기록해준다.
            result[i - 1][j - 1] = value;
            result[j - 1][i - 1] = value;
        }
    }

    return result;
}

Reference

https://velog.io/@eunseo_thatsme/KnightL-on-a-Chessboard