프로그래머스 석유 시추

문제

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

---

한 열을 수직으로 뚫는 시추관에서 한 번 뚫었을 때 가장 많이 받을 수 있는 석유의 양을 계산하는 문제 맨 처음에는 그냥 루프 돌아서 석유만 골라내면 되는거 아닌가 생각했지만,, 석유가 이어져 있을 경우 이어져있는 석유가 모두 들어오기 때문에 이에 대해서도 계산이 필요함

시도 1. 루프를 돌다가 석유를 만다면 DFS로 석유의 양을 계산하여 열별로 최댓값 계산

DFS로 석유의 양을 계산한다고 하면 지나간 길을 표시해야 하는데, 이걸 얕은 복사로 해버리면 다음 열에서 시추를 할 때 지나간 길이 표시된 석유의 경우 판단하기 어렵다 그렇다고 깊은 복사로 해버리면, 열을 도는 과정에서

시도2. DFS로 모두 탐색한 다음, 해당하는 열에 대해서 정보를 기록

function solution(land) {
    const oilMap = new Map();
    land.forEach((rowArr,row) => {
        rowArr.forEach((colArr, col) => {
            const oilRoad = [];
            const drilled = drilling(oilMap, land, row, col, oilRoad);
            oilRoad.forEach((oiledCol) => {
                if(oilMap.has(oiledCol)) oilMap.set(oiledCol,oilMap.get(oiledCol) + drilled);
                else oilMap.set(oiledCol, drilled);  
            })
        })
    })  
    let max = 0;
    for (let val of oilMap.values()){
        if(max<val) max = val;
    }
    return max;
}
 
 
 
function drilling(oilMap,land,row,col,road){
    if(!land[row][col]) return 0;
    if(!road.includes(col)) road.push(col);
    land[row][col] = 0;
    let oils = 1;
    // dfs
    if(row > 0) oils += drilling(oilMap,land, row-1, col, road);
    if(row<land.length-1) oils += drilling(oilMap, land, row+1, col, road);
    if(col > 0) oils += drilling(oilMap,land, row, col-1,  road);
    if(col<land[0].length-1) oils += drilling(oilMap, land, row, col+1,  road);
    return oils;
}

이런 식으로 dfs 탐색을 하면서 지나간 자리를 0으로 만들고, 지나갔던 열에 대해서 모두 배열에 넣은 뒤에 map에서 col의 키값에 해당 석유 덩이의 크기만큼을 더해주는 방식으로 순회를 돌고, 마지막에는 만들어진 map에 대해서 최댓값을 찾도록 했다.

정확성 테스트는 모두 통과했으나, 효율성 테스트에서는 2개가 런타임 에러가 떴다. 다른 사람들이 질문한 것을 보았을 때, 아마 재귀가 깊어지면서 나오는 에러때문이 아닐까 싶었다.

시도 3. BFS로 탐색한 후에 해당하는 열에 대해서 기록

function solution(land) {
    const oilMap = new Map();
    
    for (let row = 0; row < land.length; row++) {
        for (let col = 0; col < land[row].length; col++) {
            if (land[row][col]) {
                const oilRoad = [];
                const drilled = drilling(oilMap, land, row, col, oilRoad);
 
                oilRoad.forEach((oiledCol) => {
                    if (oilMap.has(oiledCol)) {
                        oilMap.set(oiledCol, oilMap.get(oiledCol) + drilled);
                    } else {
                        oilMap.set(oiledCol, drilled);
                    }
                });
            }
        }
    }
 
    let max = 0;
    for (let val of oilMap.values()) {
        if (max < val) max = val;
    }
 
    return max;
}
 
function drilling(oilMap, land, startRow, startCol, road) {
    const queue = [[startRow, startCol]];
    let oils = 0;
 
    while (queue.length > 0) {
        const [row, col] = queue.shift();
 
        if (land[row][col] === 0) continue;
 
        oils++;
        land[row][col] = 0;
 
        if (!road.includes(col)) road.push(col);
 
        if (row > 0 && land[row - 1][col]) queue.push([row - 1, col]);
        if (row < land.length - 1 && land[row + 1][col]) queue.push([row + 1, col]);
        if (col > 0 && land[row][col - 1]) queue.push([row, col - 1]);
        if (col < land[0].length - 1 && land[row][col + 1]) queue.push([row, col + 1]);
    }
 
    return oils;
}

이번에는 BFS를 활용하여 문제를 풀었을 때 모두 정답이 떴다. BFS의 경우에는 재귀를 이용하지 않고 큐를 이용하기 때문에, 런타임 에러가 발생하지 않아 정답이 뜬 것으로 보인다.