[JS] 프로그래머스 수레 움직이기

https://school.programmers.co.kr/learn/courses/30/lessons/250134?language=javascript

프로그래머스

 

참고로 방법 1은 dfs + 백트래킹이다.

방법 1의 경우 2차원 배열을 두 개 만들어 놓고 false, true 왔다 갔다 백트래킹으로 풀면 되었다.

그러나 방법 1은 무조건 완전 탐색이므로 시간이 좀 더 걸린다.

따라서 방법 2의 무조건 빨간색, 파란색 수레 모두 도착하는 경우 바로 cnt를 반환하도록 구현하였다.

 

비트마스킹의 경우 정수를 사용한다. (배열 - 공간복잡도 초과, 문자열 - 문자열은 바꿀 수 없음 -> 공간복잡도 증가)

먼저 0으로 초기화한 후에 원하는 인덱스를 시프트 연산으로 하면 된다.

(1을 넣고 싶다면 비트마스크 |= (1 << 원하는 인덱스);

 0을 넣고 싶다면 비트마스크 &= (0 << 원하는 인덱스);

 반대값을 넣고 싶다면 비트마스크 ^= (1 << 원하는 인덱스)  -> XOR 연산 같으면 0, 다르면 1)

문제에서는 가로 세로 길이가 최대 4이었으므로 4*4 최대 16인 길이가 되었다. (비트마스킹 사용 가능)

 

따라서 갈 수 있는 경우를 0으로 하고 갈 수 없는 경우를 1로 하고 나서 dfs + 백트래킹과 같은 방식으로 풀었다.

(대신에 visited 배열을 사용하지 않고 이를 비트마스킹으로 풀었다. 나머지는 같다.)

 

// 방법 2 : bfs + 비트마스킹

function solution(maze) {
    const n = maze.length;
    const m = maze[0].length;
    
    let rStart, bStart, rEnd, bEnd;
    let rStartMask = 0; 
    let bStartMask = 0;
    
    for (let r = 0; r < n; r++) {
        for (let c = 0; c < m; c++) {
            const idx = r * m + c;
            
            if (maze[r][c] === 5) {
                rStartMask |= (1 << idx);
                bStartMask |= (1 << idx);
            } else if (maze[r][c] === 1) rStart = [r, c];
            else if (maze[r][c] === 2) bStart = [r, c];
            else if (maze[r][c] === 3) rEnd = [r, c];
            else if (maze[r][c] === 4) bEnd = [r, c];
        }
    }
    
    rStartMask |= (1 << (rStart[0] * m + rStart[1]));
    bStartMask |= (1 << (bStart[0] * m + bStart[1]));
    
    const queue = [[rStart, bStart, rStartMask, bStartMask, 0]];
    let head = 0;
    
    const dr = [0, 0, 1, -1];
    const dc = [1, -1, 0, 0];
    
    while (head < queue.length) {
        const [rPos, bPos, rMask, bMask, cnt] = queue[head++];
        
        const rArrived = rPos[0] === rEnd[0] && rPos[1] === rEnd[1] ? true : false;
        const bArrived = bPos[0] === bEnd[0] && bPos[1] === bEnd[1] ? true : false;
        
        if (rArrived && bArrived) return cnt;
        
        // 1. 파란색만 이동
        if (rArrived) {
            for (let i = 0; i < 4; i++) {
                const nr = bPos[0] + dr[i];
                const nc = bPos[1] + dc[i];
                
                if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
                
                const ni = nr * m + nc;
                
                if ((bMask & (1 << ni)) !== 0) continue;
                
                if (nr === rPos[0] && nc === rPos[1]) continue;
                
                const nextMask = bMask | (1 << ni);
                queue.push([rPos, [nr, nc], rMask, nextMask, cnt + 1]);
                
            }
        }
        
        // 2. 빨간색만 이동
        else if (bArrived) {
            for (let i = 0; i < 4; i++) {
                const nr = rPos[0] + dr[i];
                const nc = rPos[1] + dc[i];
                
                if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
                
                const ni = nr * m + nc;
                
                if ((rMask & (1 << ni)) !== 0) continue;
                
                if (nr === bPos[0] && nc === bPos[1]) continue;
                
                const nextMask = rMask | (1 << ni);
                queue.push([[nr, nc], bPos, nextMask, bMask, cnt + 1]);
                
            }
        }
        
        // 3. 둘 다 이동
        else {
            for (let i = 0; i < 4; i++) {
                const rnr = rPos[0] + dr[i];
                const rnc = rPos[1] + dc[i];
                
                if (rnr < 0 || rnr >= n || rnc < 0 || rnc >= m) continue;
                
                const rni = rnr * m + rnc;
                
                if ((rMask & (1 << rni)) !== 0) continue;
                
                const nextRMask = rMask | (1 << rni);
                
                for (let j = 0; j < 4; j++) {
                    const bnr = bPos[0] + dr[j];
                    const bnc = bPos[1] + dc[j];
                    
                    if (bnr < 0 || bnr >= n || bnc < 0 || bnc >= m) continue;
                
                    const bni = bnr * m + bnc;

                    if ((bMask & (1 << bni)) !== 0) continue;
                    
                    const nextBMask = bMask | (1 << bni);
                    
                    // 교차하는 경우
                    if (bnr === rPos[0] && bnc === rPos[1] &&
                       rnr === bPos[0] && rnc === bPos[1]) continue;
                    // 같은 곳으로 가는 경우
                    if (bnr === rnr && bnc === rnc) continue;
                    
                    queue.push([[rnr, rnc], [bnr, bnc], nextRMask, nextBMask, cnt + 1]);
                }

            }
        }
    }
    
    return 0;
}