[프로그래머스][bfs] 석유시추

     

목차

 

문제

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

프로그래머스

 

문제 구현 방향

나는 먼저 시추가 있는 부분을 전처리 해서 영역의 크기를 반영해 따로 배열을 만들어 주었다.

이때 주의할점은 나는 영역을 구분하기 위해 유니크한 값도 같이 배열로 넣었다.

 

function bfs(sX, sY, land, visit,  col, row){
    let queue =[];
    queue.push([sX, sY]);
    save.push([sX, sY]);
    visit[sY][sX] = 1;
    let cnt =1;
    while(queue.length){
       let [curX, curY] = queue.shift();
       for(let [dx, dy] of dir){
           let x = curX +dx;
           let y = curY +dy;
           if(x >col-1 || x < 0 || y > row-1 || y < 0)continue;
           if(visit[y][x] || land[y][x] === 0) continue;
           cnt++;
           visit[y][x] = 1;
           queue.push([x, y]);
           save.push([x, y]);
    }
    }
    return cnt;
   
}

for(let i=0; i< row; i++){
        for(let j=0; j< col; j++){
            if(!visit[i][j] && land[i][j] ===1){
               let cnt= bfs(j, i, land, visit,  col, row);
                for(let s of save){
                    let [x, y] = s;
                    //유니크한 값 추가 
                    board[y][x] = [cnt, unq];
                }
                save =[];
                unq++;
            }
        }
    }

 

그 후에 탐색 과정에서  set을 통해 한 열마다 set에 있는지 없는지 판단하는 식으로 풀었다.

let ans = new Array(col).fill(0);
    
    for(let i=0; i< col; i++){
        let h =0;
        let cnt =0;
        let s = new Set();
        while(h< row){
            if(board[h][i]!==0 && !s.has(board[h][i][1]) ){
                s.add(board[h][i][1]);
                cnt +=board[h][i][0];
            }
            h++;
        }
        ans[i] = cnt;
    }
    answer = Math.max(...ans);

 

 

코드 구현

let dir = [[-1, 0], [1, 0], [0, -1], [0, 1]];
let save =[];

function bfs(sX, sY, land, visit,  col, row){
    let queue =[];
    queue.push([sX, sY]);
    save.push([sX, sY]);
    visit[sY][sX] = 1;
    let cnt =1;
    while(queue.length){
       let [curX, curY] = queue.shift();
       for(let [dx, dy] of dir){
           let x = curX +dx;
           let y = curY +dy;
           if(x >col-1 || x < 0 || y > row-1 || y < 0)continue;
           if(visit[y][x] || land[y][x] === 0) continue;
           cnt++;
           visit[y][x] = 1;
           queue.push([x, y]);
           save.push([x, y]);
    }
    }
    return cnt;
   
}

function solution(land) {
    var answer = 0;
    let col = land[0].length;
    let row = land.length;
    let visit = Array.from({length: row}, ()=> Array(col).fill(0));
    let board = [...land];
    let unq = 0;
    for(let i=0; i< row; i++){
        for(let j=0; j< col; j++){
            if(!visit[i][j] && land[i][j] ===1){
               let cnt= bfs(j, i, land, visit,  col, row);
                for(let s of save){
                    let [x, y] = s;
                    board[y][x] = [cnt, unq];
                }
                save =[];
                unq++;
            }
        }
    }
    let ans = new Array(col).fill(0);
    
    for(let i=0; i< col; i++){
        let h =0;
        let cnt =0;
        let s = new Set();
        while(h< row){
            if(board[h][i]!==0 && !s.has(board[h][i][1]) ){
                s.add(board[h][i][1]);
                cnt +=board[h][i][0];
            }
            h++;
        }
        ans[i] = cnt;
    }
    answer = Math.max(...ans);
    return answer;
}