프로그래머스 [Lv. 3] 블록 이동하기 {언어 : JavaScript} [다시 풀어 보기]

문제 링크

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

프로그래머스

정답 코드

function solution(board) {
    let answer = 0;
    const n = board.length;
    const [er, ec] = [n-1, n-1];
    
    const dr = [-1, 1, 0, 0];
    const dc = [0, 0, -1, 1];
    
    const isValid = (nr, nc) => {
        return 0 <= nr && nr < n && 0 <= nc && nc < n && board[nr][nc] == 0;
    }
    
    const makeKey = (nr, nc, np, nq) => {
        return `${nr},${nc},${np},${nq}`;
    }
    
    const visited = new Set();
    const dq = [];
    
    const pushQ = (nr, nc, np, nq, time) => {
        const newKey = makeKey(nr, nc, np, nq);
        if (!visited.has(newKey)) {
            visited.add(newKey);
            dq.push([nr, nc, np, nq, time + 1]);
        }
        return;
    }
    
    pushQ(0, 0, 0, 1, -1);
    
    while (dq.length) {
        const [r, c, p, q, time] = dq.shift();
        if ((r === er && c === ec) || (p === er && q === ec)) {
            answer = time;
            break;
        }
        
        const shape = r === p ? 1 : 0; // 1 means horizontal
        
        if (shape) { // Horizontal
            for (let d = 0; d < 2; d++) {
                const nr = r + dr[d];
                const np = p + dr[d];
                if (isValid(nr, c) && isValid(np, q)) {
                    pushQ(nr, c, np, q, time);
                    pushQ(nr, c, r, c, time);
                    pushQ(np, q, p, q, time);
                }
            }
            for (let d = 2; d < 4; d++) {
                const nc = c + dc[d];
                const nq = q + dc[d];
                if (isValid(r, nc)) {
                    pushQ(r, nc, r, c, time);
                }
                if (isValid(p, nq)) {
                    pushQ(p, nq, p, q, time);
                }
            }
        } else { // Vertical
            for (let d = 2; d < 4; d++) {
                const nc = c + dc[d];
                const nq = q + dc[d];
                if (isValid(r, nc) && isValid(p, nq)) {
                    pushQ(r, nc, p, nq, time);
                    pushQ(r, nc, r, c, time);
                    pushQ(p, nq, p, q, time);
                }
            }
            for (let d = 0; d < 2; d++) {
                const nr = r + dr[d];
                const np = p + dr[d];
                if (isValid(nr, c)) {
                    pushQ(nr, c, r, c, time);
                }
                if (isValid(np, q)) {
                    pushQ(np, q, p, q, time);
                }
            }
        }
    }
    
    return answer;
}

풀이 방법

 변수 및 상수 

• n: 보드의 크기.
• er, ec: 종료 지점의 행과 열 좌표.
• dr, dc: 상하좌우 이동을 나타내는 배열.
• isValid: 주어진 좌표가 보드 내에 있고, 벽이 아닌지를 확인하는 함수.
• makeKey: 로봇의 상태를 나타내는 고유 키를 생성하는 함수.
• visited: 방문한 상태를 기록하는 집합(Set).
• dq: BFS를 위한 큐.

 함수 

• pushQ: 새로운 상태를 큐에 추가하고 방문 기록에 추가하는 함수. (상태는 로봇의 두 좌표와 시간을 포함)

 로직 

1. 초기화:
   • 초기 상태 (0, 0, 0, 1, 0)를 큐에 추가하고 방문 기록에 저장한다.
2. BFS 탐색:
   • 큐가 빌 때까지 반복한다.
   • 현재 상태를 큐에서 꺼낸다.
   • 현재 상태가 종료 지점에 도달하면 종료하고 시간을 반환한다.
3. 이동 및 회전:
   • 로봇이 가로로 있는 경우와 세로로 있는 경우를 나누어 처리한다.
   • 각 경우에 대해 상하좌우 이동을 시도하고, 이동이 가능하면 새로운 상태를 큐에 추가한다.
   • 로봇의 회전도 시도하여 가능한 경우 새로운 상태를 큐에 추가한다.
4. 결과 반환:
   • 종료 지점에 도달하면 최소 시간을 반환하면 끝!

느낀점

• 꼼꼼하게 풀었다고 생각했는데 중복제거 방문배열 부분에서 실수했다.

실수한 부분

const makeKey = (nr, nc, np, nq) => {
    return "key" + nr + nc + np + nq;
}

const makeKey = (nr, nc, np, nq) => {
    return `${nr},${nc},${np},${nq}`;
}

• 처음에 중복 될 것 같아서 nr _ nc _ np _ nq 이렇게 했으면서 그냥 대충 nr + nc + np + nq로 하는 바람에 중복제거가 되지 않았고 결국 틀렸다.