[프로그래머스] 250134 [PCCP 기출문제] 4번 / 수레 움직이기 (javascript)

문제

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

풀이

N, M의 크기가 최대 4인 것을 보고 BFS로 풀어야겠다고 결정했다. 처음에는 문제를 제대로 읽지 않고 N, M이 클 것이라고 생각한 채 한 시간 정도 아이디어를 떠올렸는데, 마땅한 방법이 없었다. 아직도 N, M이 충분히 크다면 어떻게 풀어야 할지는 잘 모르겠다. 두 수레가 동시에 움직이고, 각자 방문 제약까지 있어서 상태가 너무 빠르게 커질 것 같았다. 애초에 큰 입력을 염두에 둔 문제가 아닌 것 같기도 하다.

이 문제는 두 수레가 모두 도착해야 비로소 의미 있는 종료 상태가 만들어진다. 그래서 지역 최적해를 구하거나 각 상태를 독립적으로 처리하는 접근은 큰 의미가 없었다. 다행히 N, M이 충분히 작았기 때문에, 그냥 BFS로 구현했다.

가장 까다로웠던 부분은 두 수레가 같은 칸에 동시에 도착하는 경우를 처리하는 것이었다. 다만 시간 복잡도가 충분히 감당 가능해 보여서, 각 수레의 후보 칸을 먼저 뽑은 뒤 이중 for문으로 가능한 상태를 조합해 큐에 넣는 방식으로 처리했다. 종료 조건의 위치도 꽤 애매했다. while문의 맨 앞이나 맨 뒤에 두고 싶었지만 어느 쪽도 딱 맞는 느낌이 아니었다. 결국 내부 for문 안에 넣었는데, 한눈에 이해되지는 않더라도 불필요하게 코드를 더 늘리고 싶지 않아서 그렇게 정리했다.

서로 엇갈리는 경우를 확인할 수 있는 테스트케이스가 제공된 점도 도움이 컸다. 그게 없었다면 어디서, 왜 틀렸는지도 모른 채 아주 오래 디버깅했을 것 같다.

전체적으로는 꽤 난해한 문제였다. 그럼에도 출제자가 필요한 부분에서는 친절하게 배려해줬다는 느낌이 있었고, 덕분에 생각보다 어렵지 않게 풀 수 있었다.

정답 코드

javascript

const CELL = OBJECT.freeze({
    EMPTY: 0,
    RED_START: 1,
    BLUE_START: 2,
    RED_GOAL: 3,
    BLUE_GOAL: 4,
    WALL: 5
});
const DIRECTIONS = [ [-1, 0], [0, 1], [1, 0], [0, -1] ];

const solution = (maze) => {
    let ret = 0;
    
    const N = maze.length;
    const M = maze[0].length;
    
    const toBit = ([ r, c ]) => (1 << (M * r + c));
    const mask = (bit, pos) => bit | toBit(pos);
    const isVisited = (visited, pos) => visited & toBit(pos);
    const outOfRange = (r, c) => r < 0 || N <= r || c < 0 || M <= c;
    const isSamePos = (pos1, pos2) => pos1[0] === pos2[0] && pos1[1] === pos2[1];
    
    const getStartState = () => {
        const ret = Array(2);
    
        for (let i = 0; i < maze.length; i++) {
            for (let j = 0; j < maze[i].length; j++) {
                const cell = maze[i][j];
            
                if (cell === CELL.RED_START || cell === CELL.BLUE_START) {
                    ret[cell - 1] = [ [i, j], toBit([i, j]) ];
               }
            }
        }
    
        return ret;
    }
    
    const getNextStates = (currentState) => DIRECTIONS.map(([ dr, dc ]) => {
        const [ pos, visited ] = currentState;
        const [ r, c ] = pos;
        const nr = r + dr;
        const nc = c + dc;
        const nextPos = [ nr, nc ];
        const canMove = !outOfRange(nr, nc) && maze[nr][nc] !== CELL.WALL && !isVisited(visited, nextPos)
    
        return canMove ? [ nextPos, mask(visited, nextPos) ] : null;
    }).filter((state) => state !== null);

    const queue = [getStartState()];
    
    while (0 < queue.length) {
        const length = queue.length;
        
        for (let i = 0; i < length; i++) {
            const [ rCurrentState, bCurrentState ] = queue.shift();
            const [ rPos, rVisited ] = rCurrentState;
            const [ bPos, bVisited ] = bCurrentState;
            const [ rr, rc ] = rPos;
            const [ br, bc ] = bPos;
            const rArrived = maze[rr][rc] === CELL.RED_GOAL;
            const bArrived = maze[br][bc] === CELL.BLUE_GOAL;
            
            if (rArrived && bArrived) {
                return ret;
            }
            
            const rNextStates = rArrived ? [rCurrentState] : getNextStates(rCurrentState);
            const bNextStates = bArrived ? [bCurrentState] : getNextStates(bCurrentState);
            
            for (const rNextState of rNextStates) {
                const [ rNextPos, rNextVisited ] = rNextState;
                
                for (const bNextState of bNextStates) {
                    const [ bNextPos, bNextVisited ] = bNextState;
                    const isSwitched = isSamePos(bPos, rNextPos) && isSamePos(rPos, bNextPos);
                    const isCollapsed = isSamePos(rNextPos, bNextPos);
                    
                    if (!isSwitched && !isCollapsed) {
                        queue.push([ rNextState, bNextState ]);
                    }
                }
            }
        }
        
        ret++;
    }
    
    return 0;
}

[프로그래머스] 250134 [PCCP 기출문제] 4번 / 수레 움직이기 (javascript)

문제

풀이

정답 코드

Share this post