[PCCP 기출문제] 2번 석유시추(lv2, js)

간만에 머리도 풀어볼 겸, 프로그래머스에서 알고리즘 문제를 풀어봤다. 
lv1은 쉽게 풀었지만, 2에서는 효율성에서 실패가 떴고 푸는데 조금 고민을 하게 되어 정리를 해보고자 한다.

 

 

문제 링크는 다음과 같다.

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

프로그래머스

function solution(land) {
    var answer = 0;
    const depth = land.length;
    const width = land[0].length;

    //이중배열 깊은 복사
    const visitedMap = land.map(_ => new Array(width).fill(0));

    let oilIdx = 1

    const oilMap = new Map();
    const directions = [[-1, 0], [1, 0], [0, 1], [0, -1]]

    function bfs(y, x) {
        let oil = 0;
        const queue = [[y, x]];
        visitedMap[y][x] = oilIdx

        while (queue.length > 0) {
            const [cy, cx] = queue.shift();
            if (land[cy][cx] === 1) {
                oil++;
            }

            //주변 가능한 곳 탐색 후, 연결된 oil들은 모두 oilIndex 표시
            for (const [dy, dx] of directions) {
                const y = cy + dy;
                const x = cx + dx;
                if (y < 0 || x < 0 || y >= depth || x >= width || visitedMap[y][x] !== 0 ) {
                    continue;
                }

                if (land[y][x]) {
                    visitedMap[y][x] = oilIdx;
                    queue.push([y, x]);
                }
            }
        }

        oilMap[oilIdx] = oil;
        oilIdx++;
        return oil;
    }

    for (let x = 0; x < width; x++){
        for (let y = 0; y < depth; y++){
            //한번 석유 덩어리를 확인한 경우 또 확인 할 필요가 없다.
            if (visitedMap[y][x] === 0 && land[y][x] > 0) {
                bfs(y, x);
            }
        }
    }

    //visitedMap을 완성 시킨 다음, 순회하며 가장 많은 오일량을 뽑을 수 있는 위치를 찾아낸다.
    for (let x = 0; x < width; x++){
        let oilVolume = 0;
        const set = new Set();
        for (let y = 0; y < depth; y++){
            const oilIdx = visitedMap[y][x];
            if (oilIdx !== 0 && !set.has(oilIdx)) {
                set.add(visitedMap[y][x])
            }
        }
        set.forEach(oid => {
            oilVolume += oilMap[oid];
        })

        answer = answer <= oilVolume ? oilVolume : answer
    }

    return answer;
}

 

 

 

주요하게 볼 점은 bfs를 통해서 지도 덩어리 맵(visitedMap)을 완성 시키는 부분이다.

처음에는 저렇게 방문한 것을 기록하지 않고 거의 brute-force 처럼 풀어서 정확도는 통과 했지만, 효율성은 통과하지 못했다. 

 

간만에 푸니, 옛날에 풀었던 기억이 가물가물해서 자주 풀어봐야 겠다는 생각이 들었다.