프로그래머스 [Lv. 2] 지게차와 크레인 {언어 : JavaScript}

문제 링크

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

프로그래머스

정답 코드

function solution(storage, requests) {
    let cnt = 0;
    
    const n = storage.length;
    const m = storage.at(0).length;
    const di = [-1, 1, 0, 0];
    const dj = [0, 0, -1, 1];
    const isValid = (ni, nj) => {
        return 0 <= ni && ni < n+2 && 0 <= nj && nj < m+2;
    }
    
    const board = Array.from({length: n+2}, () => Array(m+2).fill(0));
    for (let i = 1; i < n+1; i++) {
        for (let j = 1; j < m+1; j++) {
            const ascii = storage.at(i-1).at(j-1).charCodeAt();
            board[i][j] = ascii - 64;
        }
    }
    
    requests.forEach((e) => {
        const lenE = e.length;
        const selected = e.at(0).charCodeAt() - 64;
        if (lenE === 2) {
            for (let i = 1; i < n+2; i++) {
                for (let j = 1; j < m+2; j++) {
                    if (board.at(i).at(j) === selected) {
                        board[i][j] = -1;
                        cnt++;
                    }
                }
            }
        } else {
            const stack = [];
            // -1이 있는 부분 중에 0이랑 닿는 부분 0으로 만들기
            const visited = Array.from({length: n+2}, () => Array(m+2).fill(0));
            const queue = [[0, 0]];
            while (queue.length > 0) {
                const [i, j] = queue.shift();
                for (let d = 0; d < 4; d++) {
                    const ni = i + di[d];
                    const nj = j + dj[d];
                    if (isValid(ni, nj) && visited.at(ni).at(nj) === 0) {
                        const banianj = board.at(ni).at(nj);
                        if (banianj === 0) {
                            queue.push([ni, nj]);
                            visited[ni][nj] = 1;
                        } else if (banianj === -1) {
                            queue.push([ni, nj]);
                            visited[ni][nj] = 1;
                            board[ni][nj] = 0;
                        }
                    }
                }
            }
            // 0이랑 닿는 부분 stack에 넣기
            for (let i = 1; i < n+2; i++) {
                for (let j = 1; j < m+2; j++) {
                    const baiaj = board.at(i).at(j);
                    if (baiaj === selected) {
                        for (let d = 0; d < 4; d++) {
                            const ni = i + di[d];
                            const nj = j + dj[d];
                            if (isValid(ni, nj) && board.at(ni).at(nj) === 0) {
                                stack.push([i, j])
                                break;
                            }
                        }
                    }
                }
            }
            cnt += stack.length;
            stack.forEach(([i, j]) => {
                board[i][j] = 0;
            })
        }
    })
    const answer = n * m - cnt;
    return answer;
}

풀이 방법

1. 스토리지를 0으로 감싸서 더 큰 배열을 만든다.
   • 이렇게 해서 바깥 부분을 특정지을 수 있다.
2. 0과 닿는 부분을 지우고 0으로 만든다.
3. 모두 지울 수 있는 경우 -1로 만들고 0과 닿았는지 확인하여 -1이 0과 닿았으면 0으로 바꿔준다.
   • -1이 바깥이 된 경우 언제까지나 -1로 있을 수는 없다.
4. 이런식으로 계산해서 남는 부분의 개수를 출력하면 끝!

느낀점

• 오랜만에 풀면 array 설정 방법도 헷갈린다.
• bfs로 푸는 방법을 떠올렸으나 크레인으로 뺀 부분을 어떻게 처리 해야할지 고민했었다.