[프로그래머스] 지게차와 크레인

 

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

프로그래머스

request가 단일 문자로 올경우 테두리와 붙어있는 요청 문자를 제거하기 때문에 탐색이 필요하다고 생각함

 

문제에서 주어진 storage로만 이용해서 탐색하기엔 처음 기준이 없다고 생각하여 storage에 테두리를 추가하여 탐색하는 아이디어를 떠올림

 

두 번 반복된 문자의 요청이 올 경우 간단히 storage를 돌아 replaceAll 해주면 됨

 

requests의 반복이 진행될 때마다 다시 탐색해야 하기 때문에 반복문 상단에서 탐색 변수 초기화

 

처음 initVisited라는 변수에 visited 초기값을 넣어두고 반복문이 진행될 때마다 isVisited에 할당했는데 얕은 복사로 인해 정상 동작하지 않아 반복문이 진행될 때 재할당해서 사용하는 것으로 수정

• visited는 이중 배열이기 때문에 바깥 배열의 slice()가 아닌 내부배열에서 slice()를 하여 해결할 수 있음

 

인덱스로 접근하여 수정하는 방식을 쓰다가 해당 문제는 문자열로 이루어져 있는 배열이라는 것을 떠올리고 필요한 부분은 잘라 수정하는 것으로 수정

function solution(storage, requests) {
    var answer = 0;
    
    const dx = [-1, 1, 0, 0];
    const dy = [0, 0, 1, -1];
    
    let map = storage.map(row => "@" + row + "@")
    map.unshift("@".repeat(map[0].length));
    map.push("@".repeat(map[0].length));
    
    let isVisited = Array.from(Array(map.length), () => Array(map[0].length).fill(false));
    
    const stack = [];
    
    requests.forEach((req, idx) => {
        isVisited = Array.from(Array(map.length), () => Array(map[0].length).fill(false));
        isVisited[0][0] = true;
        stack.push([0, 0, map[0][0]]);
        
        if(req.length == 1){
            while(stack.length > 0){
                const [row, col, cont] = stack.pop();                
                
                for(let i = 0; i < dx.length; i++){
                    const nextR = row + dy[i];
                    const nextC = col + dx[i];
                    
                    if(!(nextR >= 0 && nextR < map.length && nextC >= 0 && nextC < map[0].length)) continue;
                    if(isVisited[nextR][nextC]) continue;
                    
                    if(map[nextR][nextC] == req){
                        isVisited[nextR][nextC] = true;
                        map[nextR] = map[nextR].slice(0, nextC) + "@" + map[nextR].slice(nextC + 1);
                        continue;
                    }
                    
                    if(map[nextR][nextC] != "@") continue;
                    
                    isVisited[nextR][nextC] = true;
                    stack.push([nextR, nextC, map[nextR][nextC]]);
                }
            }
        } else {
            const remove = req[0];
            map = map.map(row => row.replaceAll(remove, "@"));
        }
    })
    
    map.forEach(row => {
        answer += (row.length - (row.split("@").length - 1))
    })
    
    return answer;
}