[프로그래머스 Lv3] 지게차와 크레인 - Javascript 풀이

 

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

프로그래머스

---

문제

특정 컨테이너를 꺼낸 후 남은 컨테이너의 개수 구하는 문제

 

생각

BFS를 응용해서 지게차가 접근 가능 공간을 큐에 넣고, 

그 주변에 특정 컨테이너가 있다면 꺼내는 방식으로 접근했다.

 

일반적인 BFS라면 "특정 컨테이너가 있다면 꺼내고 해당 공간을 큐에 다시 넣어 확장" 해야하는데,

이 문제는 작업 공간의 너비가 1로 제한된다는 점이 달랐다.

 

또한, 크레인으로 컨테이너를 꺼낸 뒤

그로 인해 새롭게 접근 가능한 공간을 어떻게 표시할 지도 고민이 필요했다.

 

시간 복잡도는 O(R x n x m)으로 효율적이라 생각했다.

 

문제풀이

지게차 작업일 경우 → bfs를 호출한다.

크레인 작업일 경우 → 배열을 순회하며 특정 컨테이너 vis[i][j]에 2를 저장한다.

 

vis에서 0, 1, 2는 다음과 같은 의미를 가진다.

0	남은 컨테이너
1	컨테이너를 치운 후 접근 가능한 공간
2	크레인을 이용해 컨테이너를 치운 공간 ( = 접근 가능한 공간 후보 )

 

접근 가능한 공간을 큐에 넣는다.

- 컨테이너 전체를 둘러싼 가상의 외곽 공간을 큐에 넣는다.

if ( i == -1 || i == n || j == -1 || j == m ) queue.push([i, j])

 

 

- 이전 작업으로 인해 접근 가능하게 된 공간을 큐에 넣는다. 

if ( vis[i][j] == 1 ) queue.push([i, j])

 

BFS 탐색과정

해당 공간의 상하좌우를 탐색해 특정 컨테이너인지 확인한다.

 

- 맞다면 해당 공간에 접근 가능하다는 표시를 해준다. vis[nx][ny] = 1

- 크레인 작업으로 vis[nx][ny] = 2인 공간일 경우, 접근 가능하다는 표시 1로 바꾸어 주고 다시 큐에 넣는다.

 

코드

function solution(storage, requests) {
    const n = storage.length
    const m = storage[0].length
    
    let vis = Array.from({length : n}).map(() => Array(m).fill(0))
    var queue = []
    
    function bfs(req) {
        const dx = [0, 1, 0, -1]
        const dy = [1, 0, -1, 0]
        
        // 접근 가능한 공간일 경우 큐에 넣기
        for(let i=-1; i<=n; i++) {
            for(let j=-1; j<=m; j++) {
                if ( i == -1 || i == n || j == -1 || j == m ) {
                    queue.push([i, j])
                } else if ( vis[i][j] == 1 ) queue.push([i, j])
            }
        }
        
        // 접근 가능한 공간 상하좌우에 특정 컨테이너가 있으면 꺼냄
        while(queue.length !== 0) {
            const [curX, curY] = queue.shift() // pop()으로 써도 ok ( 더 빠름 ) 
            
            for(let dir=0; dir<4; dir++) {
                const nx = curX + dx[dir]
                const ny = curY + dy[dir]
                
                if ( nx < 0 || nx >= n || ny < 0 || ny >= m ) continue
                if ( vis[nx][ny] == 1 ) continue
                
                if ( storage[nx][ny] == req ) { // 지게차 작업 접근 가능 공간 표시
                    vis[nx][ny] = 1
                }
                if ( vis[nx][ny] == 2 ) { // 크레인 작업 후 접근 가능 공간 표시
                    vis[nx][ny] = 1
                    queue.push([nx, ny])
                }
            }
        }
    }
    
    requests.forEach((req) => {
        if ( req.length == 1 ) bfs(req)
        else {
            for(let i=0; i<n; i++) {
                for(let j=0; j<m; j++) {
                    if ( storage[i][j] == req[0] ) {
                            vis[i][j] = 2
                    }
                }
            }
        }
    })
    
    return vis.flat().filter((num) => num === 0).length
}

/*
지게차로 컨테이너를 꺼내는 경우 - 접근 가능한 컨테이너만 제거
크레인으로 컨테이너를 꺼내는 경우 - 해당 컨테이너 제거 후 접근 가능 공간인지 확인

100 * 50 * 50 
*/

 

BFS 기반 접근이므로 일반적으로는 shift()를 사용하지만,
이 문제는 탐색 너비가 1로 제한되어 있어 pop()을 사용해도 결과는 동일하다.
따라서 BFS 기반 접근이지만, DFS 방식(pop)으로 구현해도 무방하다.

(왼) pop (오) shift 시간차이