Red Knight's Shortest Path

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

문제

일반적인 체스의 나이트는 두칸 수직, 수평이동 하고 옆 또는 위아래로 한 칸씩 움직이는 이동경로를 보여준다. 이 나이트의 움직임을 커스터마이징하여 Red Knight라는 유닛을 하나 만들었고, 해당 유닛의 이동경로는 아래와 같다

[
	[0, 0,   "UL", 0, "UR", 0, 0],
  	[0, 0, 	 0,    0, 0,    0, 0],
  	[0, 0,   0,    0, 0,    0, 0],
  	[0, "L", 0,    ♟, 0,    "R", 0],
  	[0, 0,   0,    0, 0,    0, 0],
  	[0, 0,   0,    0, 0,    0, 0],
  	[0, 0,   "LL", 0, "LR", 0, 0]
]

시작 위치와 도착해야할 위치가 주어졌을 때, 최단 경로로 이동한 경로를 출력하고 도착할 수 없다면 Impossible을 반환하라.

1. 나의 풀이

최단 경로를 찾는 문제이기 때문에 bfs를 사용하여 해결하였다. 다만 이동한 경로를 알아내기 위해 queue에서 소비된 노드 정보들이 필요했고, 그것을 기록하여 마지막에 이동 경로를 찾아내 반환하도록 하였다.

function bfs(n, si, sj, ei, ej) {
    const visited = Array.from(
        new Array(n), 
        () => new Array(n).fill(false)
    );
    const queue = [[sj, si, null]];
    const px = [-1, 1, 2, 1, -1, -2],
        py = [-2, -2, 0, 2, 2, 0],
        move = ['UL', 'UR', 'R', 'LR', 'LL', 'L'];

    const spent = [];
    visited[si][sj] = true;

    while(queue.length) {
        const [x, y, parent] = queue.shift();
        spent.push([x, y, parent]);
        
        for (let i = 0; i < 6; i++) {
            const dx = x + px[i],
                dy = y + py[i];
                
            if (
                (0 <= dx && dx < n) &&
                (0 <= dy && dy < n) &&
                !visited[dy][dx]
            ) {
              	// 도착지점이라면
                if (dy === ei && dx === ej) {
                    let prevNode = spent[spent.length - 1];
                    let result = [move[i]];
                    
                    while(prevNode !== null && prevNode[2] !== null) {
                        result.push(prevNode[2].move);
                        prevNode = spent[prevNode[2].parent];
                    }
                    return result.reverse();
                }

                queue.push([dx, dy, {
                    move: move[i],
                    parent: spent.length - 1
                }]);
                visited[dy][dx] = true;
            }
        }
    }
    
    return [];
}

function printShortestPath(n, i_start, j_start, i_end, j_end) {
    // Print the distance along with the sequence of moves.
    const result = bfs(n, i_start, j_start, i_end, j_end);
    
    if (result.length) {
        console.log(`${result.length}\n${result.join(' ')}`);
    } else {
        console.log('Impossible');
    }
}

2. 다른사람의 풀이

바로 풀 수 있었던 문제들은 지금은 생략하고 추후 더 효율적인 문제 풀이법을 찾아보도록 하겠다.