프로그래머스: 블록 이동하기 - javascript(bfs 끝장내기)

문제 출처 

https://school.programmers.co.kr/learn/courses/30/lessons/60063

프로그래머스

 

정답 풀이 

그래프 최단 경로 ? bfs 알고리즘을 사용해야 되는 것은 모두 다 알거다. 

그런데 구현하기가 어려웠는데, 

그 이유는 함수화 하지 않아서 solution 기본 함수가 복잡해진 탓이라고 생각한다. 

 

또, 회전하는 경우를 

가로 => 세로 인 것과 

세로 => 가로를 구분해줘야 한다. 

 

또 이미 방문한 위치는 Set 객체를 이용하면 된다. 

정답 코드

function solution(board) {
    const dx = [-1, 1, 0, 0];
    const dy = [0, 0, -1, 1];
    const n = board.length;
    const queue = [[0, 0, 0, 1, 0]];
    const checked = new Set(['0,0,0,1']);

    while (queue.length) {
        let [x1, y1, x2, y2, time] = queue.shift();

        if ((x1 === n-1 && y1 === n-1) || (x2 === n-1 && y2 === n-1)) {
            return time;
        }

        // 상하좌우 이동
        for (let i = 0; i < 4; i++) {
            let nx1 = x1 + dx[i];
            let ny1 = y1 + dy[i];
            let nx2 = x2 + dx[i];
            let ny2 = y2 + dy[i];

            if (isValidMove(nx1, ny1, nx2, ny2, board, n) && !checked.has(`${nx1},${ny1},${nx2},${ny2}`)) {
                checked.add(`${nx1},${ny1},${nx2},${ny2}`);
                queue.push([nx1, ny1, nx2, ny2, time + 1]);
            }
        }

        // 회전 이동
        if (x1 === x2) { // 가로로 놓여 있을 때
            rotate(queue, checked, x1, y1, x2, y2, time, board, n, true);
        } else { // 세로로 놓여 있을 때
            rotate(queue, checked, x1, y1, x2, y2, time, board, n, false);
        }
    }

    return 0;

    function isValidMove(x1, y1, x2, y2, board, n) {
        return x1 >= 0 && y1 >= 0 && x2 >= 0 && y2 >= 0 &&
               x1 < n && y1 < n && x2 < n && y2 < n &&
               board[x1][y1] === 0 && board[x2][y2] === 0;
    }

    function rotate(queue, checked, x1, y1, x2, y2, time, board, n, isHorizontal) {
        const rotates = isHorizontal ?
            [[-1, 0], [1, 0]] : // 가로 -> 세로
            [[0, -1], [0, 1]];  // 세로 -> 가로

        for (let [dx, dy] of rotates) {
            const nx1 = x1 + dx;
            const ny1 = y1 + dy;
            const nx2 = x2 + dx;
            const ny2 = y2 + dy;

            if (isValidMove(nx1, ny1, x1, y1, board, n) && 
                isValidMove(nx2, ny2, x2, y2, board, n)) {

                if (!checked.has(`${nx1},${ny1},${x1},${y1}`)) {
                    checked.add(`${nx1},${ny1},${x1},${y1}`);
                    queue.push([nx1, ny1, x1, y1, time + 1]);
                }

                if (!checked.has(`${nx2},${ny2},${x2},${y2}`)) {
                    checked.add(`${nx2},${ny2},${x2},${y2}`);
                    queue.push([nx2, ny2, x2, y2, time + 1]);
                }
            }
        }
    }
}