[프로그래머스] 석유 시추

문제 내용

세로길이가 n 가로길이가 m인 격자 모양의 땅 속에서 석유가 발견되었습니다. 석유는 여러 덩어리로 나누어 묻혀있습니다. 당신이 시추관을 수직으로 단 하나만 뚫을 수 있을 때, 가장 많은 석유를 뽑을 수 있는 시추관의 위치를 찾으려고 합니다. 시추관은 열 하나를 관통하는 형태여야 하며, 열과 열 사이에 시추관을 뚫을 수 없습니다.

예를 들어 가로가 8, 세로가 5인 격자 모양의 땅 속에 위 그림처럼 석유가 발견되었다고 가정하겠습니다. 상, 하, 좌, 우로 연결된 석유는 하나의 덩어리이며, 석유 덩어리의 크기는 덩어리에 포함된 칸의 수입니다. 그림에서 석유 덩어리의 크기는 왼쪽부터 8, 7, 2입니다.

 

시추관은 위 그림처럼 설치한 위치 아래로 끝까지 뻗어나갑니다. 만약 시추관이 석유 덩어리의 일부를 지나면 해당 덩어리에 속한 모든 석유를 뽑을 수 있습니다. 시추관이 뽑을 수 있는 석유량은 시추관이 지나는 석유 덩어리들의 크기를 모두 합한 값입니다. 시추관을 설치한 위치에 따라 뽑을 수 있는 석유량은 다음과 같습니다

.

시추관의 위치획득한 덩어리총 석유량

시추관의 위치	흭득한 덩어리	총 석유량
1	[8]	8
2	[8]	8
3	[8]	8
4	[7]	7
5	[7]	7
6	[7]	7
7	[7,2]	9
8	[2]	2

 

오른쪽 그림처럼 7번 열에 시추관을 설치하면 크기가 7, 2인 덩어리의 석유를 얻어 뽑을 수 있는 석유량이 9로 가장 많습니다. 석유가 묻힌 땅과 석유 덩어리를 나타내는 2차원 정수 배열 land가 매개변수로 주어집니다. 이때 시추관 하나를 설치해 뽑을 수 있는 가장 많은 석유량을 return 하도록 solution 함수를 완성해 주세요.

문제 해결방안

BFS 방식으로 석유 그룹을 찾아서 각 카운트 값들을 진행중인 열의 값에 추가하는방식으로 진행해야한다. 효율성도 생각해야해서 bfs코드 안에서 각 col마다 석유량 그룹이 매칭되는 값 만큼 추가해줘서 해결했다.

 

bfs를 진행할때 queue에서 값을 빼는 col값을 Javascript의 Set기능으로 만약 오른쪽으로 석유그룹이 늘어나는경우에 그 늘어난곳의 값도 추가해줄수있다.

자바스크립트 코드

function solution(land) {
    let row = land.length;
    let col = land[0].length;
    
    let visited = Array.from({length: row}, () => Array(col).fill(0));

    let result = Array(col).fill(0);
    let dx = [-1,0,1,0];
    let dy = [0,1,0,-1];
    
    for(let i = 0; i < row; ++i) {
        for(let j = 0; j < col; ++j) {
            
            if(!visited[i][j] && land[i][j]) {
                let cols = new Set();
                let count = 1;
                let q = [[i,j]];
                
                while(q.length) {
                    const [x,y] = q.shift();
                    visited[x][y] = 1;
                    cols.add(y);
                    
                    for(let k = 0; k < 4; ++k) {
                        let moveX = dx[k] + x;
                        let moveY = dy[k] + y;
                        
                        if(moveX >= 0 && moveX < row && moveY >= 0 && moveY < col) {
                            if(land[moveX][moveY] && !visited[moveX][moveY]) {
                                visited[moveX][moveY] = 1;
                                q.push([moveX,moveY]);
                                count++;
                            }
                        }
                    }
                }
                for(const col of cols) {
                    result[col] += count; 
                }
            }
            
        }
    }
    
    return Math.max(...result);
}