[PCCP 기출문제] 2번 / 석유 시추 JS

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

 

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

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

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

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

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

---

 

나의 풀이

세로 열마다 석유를 찾는데, 석유가 있으면 주변을 탐색하고
하나의 항마다 가능한 석유량을 뽑고 각 항의 합을 구한다

 

• 열(col)마다 행(row)를 순회한다
• 행을 순회할 때 석유를 찾으면 연결된 총 석유량을 구하고, 연결된 열마다 이 석유량을 더한다.
  • 이 때 bfs를 통해 상하좌우를 검색하며 현재위치와 연결된 열과 해당 석유그룹의 총 석유량을 구한다.  
  •  

    

    예를 들어 위 그림의 2행0열에서 석유를 찾으면 석유량8을 연결된 열 0,1,2에 각각 더한다. 0행3열의 석유량7은 3,4,5,6 열에 더한다. 4행6열의 석유량2는 6,7 행에 더한다.

• 최종적으로 각 열마다 뽑을 수 있는 석유량이 구해지면 최대 석유량을 리턴한다.

 

느낀점

문제를 읽으면서 재귀적으로 연결된 석유량을 구하는 건 알 수 있었다. dfs, bfs중 dfs는 top-> bottom에서 다시 bottom->top으로 돌아오기 때문에 bfs가 효율적이라 생각하여 선택했다. 

한 석유그룹의 석유량을 구하면 이를 기억해서 사용할 수 있다

따라서 bfs + memory 유형이라고 생각한다.

 

주의할점

석유를 찾은 뒤에 바로 방문한 곳으로 변경 (bfs에서 잘 까먹을 수 있음 주의하자)

 

배운점

• isVisited 필요없고 바로 land를 변경한다
  • 처음에는 각 열을 검색할 때마다 land를 복사하여 isVisited 만들어서 방문한 곳을 구분했는데 생각해보니 이렇게 하면 동일한 석유 그룹을 중복하여 검색하는 것임을 깨달았다. 대신 방문한 곳은 바로 land를 변경하고 연결된 열에 석유량을 더하면 된다.
• 한 열에 여러 개의 석유 그룹이 있는 경우, 그룹마다 연결된 열이 다른 경우
  • 반례
  • 입력: [[1, 1, 1, 1, 0], [1, 0, 0, 0, 0], [0, 0, 0, 1, 1], [1, 0, 0, 1, 0], [1, 1, 0, 1, 0]] , 기댓값: 9
  • 따라서 열을 순회할 때 석유를 찾을 때마다 연결된 열의 set을 초기화해야한다.
  •  

한 열에 여러 개의 석유 그룹이 있는 경우, 그룹마다 연결된 열은 다를 수 있다.

 

---

 

function solution(land) {
    const dR = [-1, 0, 1, 0];
    const dC = [0, 1, 0, -1];
    const rLen = land.length;
    const cLen = land[0].length;
    const oilByCol = {}; //{열: 뽑을 수 있는 석유량}
    
    for (let c = 0; c < cLen; ++c) {
        const queue = [];
        
        // 한 열에서 row를 순회하며 석유 찾기
        for (let r = 0; r < rLen; ++r) {
            // 석유를 찾음. 연결된 총 석유량 구해서 oilByCol에 더하기
            if (land[r][c] === 1) {
                land[r][c] = 0; // 이미 뽑은 석유로 변경
                let sum = 1; // 석유량 초기화
                let connectedCols = new Set(); // 현재위치와 연결된 열의 set
                connectedCols.add(c);
                queue.push({r, c});
                
                // 현재위치와 연결된 열과 총 석유량 구하기
                while(queue.length) {
                    const {r, c} = queue.shift();
                    for (let i = 0; i < 4; ++i) {
                        const nextR = r + dR[i];
                        const nextC = c + dC[i];
                        
                        if (nextR >= 0 && nextR < rLen 
                            && nextC >= 0 && nextC < cLen 
                            && land[nextR][nextC] === 1
                           ) {
                            // 주변에 석유가 있고 새로운 열이면 연결된 열set에 추가
                            if (!connectedCols.has(nextC)) connectedCols.add(nextC);
                            sum++;
                            land[nextR][nextC] = 0;
                            queue.push({r: nextR, c: nextC}); // 주변열의 다음 주변을 확인한다.
                        }
                    }
                }
                // oilByCol의 연결된 열에 현재 석유그룹의 총 석유량 더하기
                for (const c of connectedCols) {
                    oilByCol[c] = (oilByCol[c] || 0) + sum;
                }  
            }
        }
    }
    const values = Array.from(Object.values(oilByCol));
    return Math.max(...values);
}

 

 

 

두번째 풀이

비슷하지만 복습차원에서 다시 풀어봤다

좀 더 로직이 간편한 것 같다

 

석유를 찾으면 연결된 곳을 다 뽑아서 배열에 더해준다

 

function solution(land) {
    const rowLen = land.length;
    const colLen = land[0].length;
    var answer = Array.from({length: land[0].length}, () => 0);
    
    for (let c = 0; c < colLen; ++c) {
        for (let r = 0; r < rowLen; ++r) {
            // 석유를 찾음
            if (land[r][c] === 1) {
                land[r][c] = 0; // !
                const {sum, connectedCols} = suckAll(r, c);
                // 연결된 곳들 석유추가
                for (const col of connectedCols) {
                    answer[col] += sum;
                }
            }
        }
    }
    
    function suckAll(r,c) {
        let sum = 1;
        const connectedCols = new Set();
        connectedCols.add(c);
        const queue = [{r,c}];
        const dr = [-1, 0, 1, 0];
        const dc = [0, 1, 0, -1];
        
        while(queue.length) {
            const {r, c} = queue.shift();
            for (let i = 0; i < 4; i++) {
                const nextR = r + dr[i];
                const nextC = c + dc[i];
                // 주변 석유를 찾음
                if (nextR >= 0 && nextR < rowLen && nextC >= 0 && nextC < colLen && land[nextR][nextC] === 1) {
                    sum++;
                    connectedCols.add(nextC);
                    land[nextR][nextC] = 0; // 방문표시
                    queue.push({r: nextR, c: nextC});
                }
            }
        }
        return {sum, connectedCols: [...connectedCols]};
    }
    return Math.max(...answer)
}