[programmers/js] 지게차와 크레인

지게차와 크레인

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

문제 설명

물류창고에는 알파벳 대문자로 종류를 구분하는 컨테이너가 세로로 n 줄, 가로로 m줄 총 n x m개 놓여 있습니다.

특정 종류 컨테이너의 출고 요청이 들어올 때마다 지게차로 창고에서 접근이 가능한 해당 종류의 컨테이너를 모두 꺼냅니다. 접근이 가능한 컨테이너란 4면 중 적어도 1면이 창고 외부와 연결된 컨테이너를 말합니다.

최근 이 물류 창고에서 창고 외부와 연결되지 않은 컨테이너도 꺼낼 수 있도록 크레인을 도입했습니다. 크레인을 사용하면 요청된 종류의 모든 컨테이너를 꺼냅니다.

이때 "A", "BB", "A" 순서대로 해당 종류의 컨테이너 출고 요청이 들어왔다고 가정하겠습니다.

1. “A”처럼 알파벳 하나로만 출고 요청이 들어올 경우 지게차를 사용해 출고 요청이 들어온 순간 접근 가능한 컨테이너를 꺼냅니다.
2. "BB"처럼 같은 알파벳이 두 번 반복된 경우는 크레인을 사용해 요청된 종류의 모든 컨테이너를 꺼냅니다.

처음 물류창고에 놓인 컨테이너의 정보를 담은 1차원 문자열 배열 storage와 출고할 컨테이너의 종류와 출고방법을 요청 순서대로 담은 1차원 문자열 배열 requests가 매개변수로 주어집니다. 이때 모든 요청을 순서대로 완료한 후 남은 컨테이너의 수를 return 하도록 solution 함수를 완성해 주세요.

풀이

제거를 요청받은 문자의 길이를 기준으로 풀이를 나눕니다.

1. 요청한 문자의 길이가 2면 배열에서 제거합니다.
2. 길이가 1이면 bfs를 통해 밖으로 꺼낼 수 있는지 확인합니다.

이때, 매번 값을 제거한 배열이 bfs에 들어가는 참조 문제가 발생하는데 깊은 복사를 통해 해결할 수 있습니다.

function solution(storage, requests) {
    const row = storage.length;
    const col = storage[0].length;
    let result = row * col;
    let storageMap = storage.map((string) => {
        return string.split("");
    });
    
    const dx = [0, 0, 1, -1];
    const dy = [1, -1, 0, 0];
    
    const bfs = (x, y, arr) => {
        const visited = Array.from({ length: row }, () => Array(col).fill(false));
        const qu = [[x, y]];
        visited[x][y] = true;
        
        while (qu.length) {
            const [cx, cy] = qu.shift();
            
            for (let i = 0; i < 4; i++) {
                const nx = cx + dx[i];
                const ny = cy + dy[i];
                
                if (nx < 0 || nx >= row || ny < 0 || ny >= col) {
                    storageMap[x][y] = ".";
                    return 1;
                }
                
                if (!visited[nx][ny] && arr[nx][ny] === ".") {
                    visited[nx][ny] = true;
                    qu.push([nx, ny]);
                }
            }
        }
        
        return 0;
    }
    
    requests.forEach((t) => {
        let currentStorage = JSON.parse(JSON.stringify(storageMap));
        if (t.length === 2) {
            for (let i = 0; i < row; i++) {
                for (let j = 0; j < col; j++) {
                    if (currentStorage[i][j] === t[0]) {
                        storageMap[i][j] = "."
                        result -= 1;
                    }
                }
            }
        } else {
            for (let i = 0; i < row; i++) {
                for (let j = 0; j < col; j++) {
                    if (currentStorage[i][j] === t[0]) {
                        result -= bfs(i, j, currentStorage); // BFS
                    }
                }
            }
        }
    });
    
    return result;
}