프로그래머스: [PCCP 기출 문제] 석유 시추 - javascript(bfs 효율성)

문제 출처 

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

프로그래머스

정답 풀이 

처음 풀이는 효율성에서 틀린 점수를 받았다. 

아래 방식으로 풀었는데, 

아무래도 checked를 가로 이동할 때마다 초기화하면서, 똑같은 곳을 bfs로 또 탐색 하게 코드를 작성했기 때문이다. 

 

따라서, 

미리 주어진 그래프로 석유가 있는 곳을 저장해놨다. 

해당 위치는 1번땅이야 ~ 2번땅이야 ~ 3번땅이야 ~ 

이것을 dp 그래프로 저장해놨다. 

- 예를 들어 dp[0][2] = 1 이 된다. 

그리고 map 객체를 생성해줬는데 

key: 땅 번호 

value: 땅 크기 

를 작성해줬다. 

 

 

 

예를 들어 아래와 같은 객체가 생성된다. 

map{

1: 8 

2: 7 

3: 2

}

 

이렇게 미리 정보를 만들어 둔후, 

이중반복문을 통해 세로를 기준으로 탐색해줬다. 

 

정답 코드 

function solution(land) {
    let n = land.length //세로
    let m = land[0].length //가로 
    let answer = 0 //답 
    const dp =  Array.from({length:n}).map(()=> new Array(m).fill(0)) //해당 위치가 몇번땅인지
    const checked = Array.from({length:n}).map(()=> new Array(m).fill(false))//방문했는지 
    let map = new Map(); //해당 땅이 가지고 있는 석유량 
    let cnt = 0; //땅 번호 
    
      for(let i=0; i<n; i++){
            for(let j=0; j<m; j++){
                if(land[i][j] === 1 && !checked[i][j]){ //석유가 있을 때 && 방문 안한 곳일 때
                    cnt++; //땅 번호 
                 let  width = bfs(i,j,checked, dp,cnt) //해당 땅에 대한 석유량 
                 map.set(cnt, width)//해당 땅 번호에 대한 석유량 저장 
                    }
                }
            }
    
    //탐색 시작 
    for(let j=0; j<m; j++){ //가로 이동 
        let set = new Set() //새로운 땅일 경우 set에 다가 넣기 (왜냐하면, 1번땅 여러번나온거 무시하기 위함) 
        let num = 0; //석유량 합한것 
        for(let i=0; i<n; i++){//세로 이동
            if(dp[i][j] !== 0) set.add(dp[i][j]) //만약 석유가 존재하는 땅일 경우 해당 땅 번호를 set에다가 넣기
        }
        let arr = [...set] //set을 배열로 변환
        for(let key of arr){//해당 땅에 대한 석유량 더하기 
            if(map.has(key)) num+= map.get(key)
        }
        answer = Math.max(num, answer) //석유량이 큰 값으로 answer에다가 계속 대체 
    }
  return answer; 


    function bfs(x,y,checked,dp,cnt){
        const dx = [-1,1,0,0]; 
        const dy = [0,0,-1,1]; 
        const queue = [[x,y]];  
        checked[x][y] = true; //방문 체크 
        let result = 0; //석유량 
        let arr = [] //석유량이 존재하는 위치 저장해야됨 
        while(queue.length){
            let [curX, curY] = queue.shift(); 
            arr.push([curX, curY])
            result++; //석유량+1
            for(let d=0; d<4; d++){
                let nx = curX + dx[d]; 
                let ny = curY + dy[d]; 
                if(nx < 0 || ny <0 || nx >= n || ny >= m) continue; 
                if(checked[nx][ny] || land[nx][ny] === 0) continue; 
                checked[nx][ny] = true
                queue.push([nx,ny])
            }
        }
        for(let [r,c] of arr){ //해당 위치들에 땅 번호 부여 
            dp[r][c] = cnt
        }
        return result //해당 땅의 석유량 
    }
}

//효율성++ 
//- 해당 부분을 map 객체로 나누자 키:idx 내가 갱신, 값: 석유 너비
//- 세로 파악할 때 해당 dp에서 map key를 적어놓자. 
//- 다른 map key일 때 값을 더해준다. 
//즉, 미리 map과 dp를 이용해 생성한 후, 그 후에 탐색을 통해 값을 구하는 방법으로다가 ~~