[Javascript/PGS] Lv.2 : 석유 시추 (PCCP 기출문제 2번)

 

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

프로그래머스

---

프로그래머스 레벨 2.

BFS 응용 문제이다

너비우선탐색으로 석유칸 수를 카운트하고, 어떤 열에서 뽑을 수 있는건지 Map에 누적한다!

코드가 길긴 했지만 크게 어려운 문제는 아니었다고 생각🤓

 

 

나의 풀이

let Land;
let n; let m;
let visited;
let dx = [0,1,0,-1];
let dy = [-1,0,1,0];
let columnMap = new Map();

const saveColumns=(columns, count)=>{
    for(let i=0; i<columns.length; ++i){
        if(columns[i]){
            columnMap.set(i,columnMap.has(i)? columnMap.get(i)+count:count);
        }
    }
}

const canVisit=(x,y)=>{
    if(x<0 || y<0 || x>=n || y>=m) return false;
    if(Land[x][y]==0) return false;
    if(visited[x][y]) return false;
    return true;
}

const bfs=(x,y)=>{
    let columns = new Array(m).fill(false);
    let q = [];
    let count = 1;
    q.push([x,y]);
    visited[x][y] = true;
    while(q.length){
        let [a,b] = q.shift();
        columns[b] = true; // 석유를 파낼 수 있는 열을 체크
        for(let i=0; i<4; ++i){
            let nx = a + dx[i];
            let ny = b + dy[i];
            if(canVisit(nx,ny)){
                q.push([nx,ny]);
                visited[nx][ny] = true;
                count++;
            }
        }
    }
    saveColumns(columns, count);
}

function solution(land) {
    var answer = 0;
    Land = land;
    n = land.length;
    m = land[0].length;
    visited = Array.from({length:n}, ()=> new Array(m).fill(false));

    for(let i=0; i<n; ++i){
        for(let j=0; j<m; ++j){
            if(!visited[i][j] && land[i][j]==1) {
                bfs(i, j);
            }
        }
    }
    
    columnMap.forEach((value)=>{
        if(answer<value) {
            answer = value;
        }
    })
    return answer;
}