석유 시추

프로그래머스 Level 2

📚 문제 설명

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

!https://grepp-programmers.s3.ap-northeast-2.amazonaws.com/files/production/beb862a9-5382-4f61-adae-bd6e9503c014/석유시추-1.drawio.png

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

!https://grepp-programmers.s3.ap-northeast-2.amazonaws.com/files/production/0b10a9f6-6d98-44d6-a342-f984ea47315c/석유시추-2.drawio.png

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

시추관의 위치 획득한 덩어리 총 석유량 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 함수를 완성해 주세요.

✅ 제한 조건

1 ≤ land의 길이 = 땅의 세로길이 = n ≤ 500
- 1 ≤ land[i]의 길이 = 땅의 가로길이 = m ≤ 500
- land[i][j]는 i+1행 j+1열 땅의 정보를 나타냅니다.
- land[i][j]는 0 또는 1입니다.
- land[i][j]가 0이면 빈 땅을, 1이면 석유가 있는 땅을 의미합니다.

정확성 테스트 케이스 제한사항

1 ≤ land의 길이 = 땅의 세로길이 = n ≤ 100
- 1 ≤ land[i]의 길이 = 땅의 가로길이 = m ≤ 100

효율성 테스트 케이스 제한사항

주어진 조건 외 추가 제한사항 없습니다.

📜 입출력 예

land result [[0, 0, 0, 1, 1, 1, 0, 0], [0, 0, 0, 0, 1, 1, 0, 0], [1, 1, 0, 0, 0, 1, 1, 0], [1, 1, 1, 0, 0, 0, 0, 0], [1, 1, 1, 0, 0, 0, 1, 1]] 9 [[1, 0, 1, 0, 1, 1], [1, 0, 1, 0, 0, 0], [1, 0, 1, 0, 0, 1], [1, 0, 0, 1, 0, 0], [1, 0, 0, 1, 0, 1], [1, 0, 0, 0, 0, 0], [1, 1, 1, 1, 1, 1]] 16

입출력 예 #1

문제의 예시와 같습니다.

입출력 예 #2

!https://grepp-programmers.s3.ap-northeast-2.amazonaws.com/files/production/5e619c77-c940-46e6-9520-e5769e49194c/석유시추-3.drawio.png

시추관을 설치한 위치에 따라 뽑을 수 있는 석유는 다음과 같습니다.

시추관의 위치 획득한 덩어리 총 석유량 1 [12] 12 2 [12] 12 3 [3, 12] 15 4 [2, 12] 14 5 [2, 12] 14 6 [2, 1, 1, 12] 16

6번 열에 시추관을 설치하면 크기가 2, 1, 1, 12인 덩어리의 석유를 얻어 뽑을 수 있는 석유량이 16으로 가장 많습니다. 따라서 16을 return 해야 합니다.

📝 작성 코드

function solution(land) {
    let [r, c] = [land.length, land[0].length];
    let visit = Array.from({length: r}, () => Array(c).fill(0));
    
    let result = Array(c).fill(0);
    let dr = [-1, 1, 0, 0];
    let dc = [0, 0, -1, 1];
    
    for (let i = 0; i < r; i++) {
        for (let j = 0; j < c; j++) {
            if (!visit[i][j] && land[i][j]) {
                let cols = new Set();
                let count = 1;
                let q = [[i, j]];
                
                while (q.length) {
                    const [x, y] = q.shift();
                    visit[x][y] = 1;
                    cols.add(y);
                    
                    for (let d = 0; d < 4; d++) {
                        let nr = dr[d] + x;
                        let nc = dc[d] + y;
                        
                        if (nr >= 0 && nr < r && nc >= 0 && nc < c) {
                            if (land[nr][nc] && !visit[nr][nc]) {
                                visit[nr][nc] = 1;
                                q.push([nr, nc]);
                                count++;
                            }
                        }
                    }
                }
                
                for (const col of cols) {
                    result[col] += count;
                }
            }
        }
    }
    
    return Math.max(...result);
}

land 배열의 행과 열을 변수 r과 c에 담아 저장한다. 방문 여부를 기록하기 위한 2차원 배열 visit을 생성해서 0으로 초기화한다. 석유가 발견된 영역을 저장할 배열인 result를 생성해서 0으로 초기화한다,

for문을 통해 land 배열을 순회한다. 만약 탐색한 부분이 석유가 존재하는 곳이고, 아직 방문하지 않았다면 석유 영역을 탐색하기 시작한다. 현재 탐색 중인 석유 영역이 포함된 열 번호를 저장하는 Set인 cols, 탐색 중인 석유 영역의 크기를 기록하는 count, BFS에 활용되는 q 배열을 생성한다. while문을 활용하여 BFS를 수행하며 석유 영역을 탐색한다.

BFS를 통해 석유 영역을 탐색하면서, 델타 배열을 활용하여 4방향으로 이동하며 탐색한다. 델타 배열을 통해 만든 새로운 위치가 유효하고, 석유가 있으면서 방문하지 않았다면 방문 처리 후 q 배열에 추가한다. 또한 count를 증가시킨다.

모든 탐색이 끝나면, 해당 영역에서 발견된 count를 cols에 포함된 col번째 열에 누적한다. 이후 result 배열에서 가장 큰 값을 반환한다.

⏰ 걸린 시간

정확성 테스트

테스트 1 〉 통과 (0.36ms, 33.5MB) 테스트 2 〉 통과 (0.42ms, 33.5MB) 테스트 3 〉 통과 (0.32ms, 33.4MB) 테스트 4 〉 통과 (0.39ms, 33.5MB) 테스트 5 〉 통과 (0.35ms, 33.6MB) 테스트 6 〉 통과 (0.77ms, 33.7MB) 테스트 7 〉 통과 (0.99ms, 33.7MB) 테스트 8 〉 통과 (0.55ms, 33.6MB) 테스트 9 〉 통과 (2.14ms, 34.3MB)

효율성 테스트

테스트 1 〉 통과 (27.63ms, 47.3MB) 테스트 2 〉 통과 (51.22ms, 51MB) 테스트 3 〉 통과 (28.24ms, 51.3MB) 테스트 4 〉 통과 (26.25ms, 47.4MB) 테스트 5 〉 통과 (56.25ms, 51.5MB) 테스트 6 〉 통과 (26.31ms, 47.5MB)