[프로그래머스 Lv2] 석유 시추 - Javascript 풀이

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

프로그래머스

---

문제

시추관을 설치했을 때 뽑을 수 있는 석유량의 최댓값을 구하는 문제

 

생각

석유가 인접한 칸들로 이루어진 덩어리를 찾기 위해

BFS나 DFS 탐색을 사용하기로 했다.

각 덩어리가 걸쳐 있는 열에 석유의 개수를 저장하기 위해,

열 단위로 석유량을 기록할 배열도 하나 필요하다.

 

문제풀이

DFS를 이용해 인접한 석유들을 하나의 덩어리로 묶는다.
각 덩어리에 대해 석유의 총 개수와 덩어리가 포함된 열의 인덱스를 집합으로 기록한다.
이후 해당 열들에 석유 개수를 더해, 열 단위로 석유량을 누적한다.

 

시간 복잡도는 land 배열을 전체 탐색하므로 → O(N x M)

 

코드

function solution(land) {
    let result = Array(land[0].length).fill(0)
    let num = 1
    let queue = []
    let vis = Array.from({length: land.length}, 
                         () => Array(land[0].length).fill(0))
    
    // 석유 덩어리 계산
    const DFS = (i, j) => {
        let cnt = 0 // 석유 덩어리 개수
        let ny_idx = new Set() // 석유 덩어리가 걸친 열 저장 
        
        const dx = [0, 1, -1, 0]
        const dy = [1, 0, 0, -1]
        
        vis[i][j] = 1
        queue.push([i, j])
        ny_idx.add(j)
        
        while(queue.length !== 0) {
            const [curX, curY] = queue.pop()
            cnt++ 
            
            for(let dir=0; dir<4; dir++) {
                const nx = curX + dx[dir]
                const ny = curY + dy[dir]
                
                if ( nx < 0 || nx >= land.length 
                    || ny < 0 || ny >= land[0].length) continue
                if ( vis[nx][ny] !== 0 || land[nx][ny] !== 1 ) continue
                
                vis[nx][ny] = 1
                queue.push([nx, ny])
                ny_idx.add(ny)
            }
        }
        
        return [cnt, ny_idx]
    }
    
    for(let i=0; i<land.length; i++) {
        for(let j=0; j<land[0].length; j++) {
            if (land[i][j] === 1 && vis[i][j] === 0) {
                const [cnt, ny_idx] = DFS(i, j)
                
                for(const ny of ny_idx) {
                    result[ny] += cnt
                }
            }
        }
    }
    
    return Math.max(...result)
}