[JS] 석유 시추

문제

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

프로그래머스

 

풀이

그냥 일반적인 BFS 문제로 처음 파악을 했다. 근데 풀어보니 틀리기도 했고 효율성 검사도 통과하지 않았다.

const bfs = (arr, x) => {
    const start = Array.from({length: arr.length}, (_, i) => [i, x]);
    
    for(let i = 0; i < start.length; i++){
        const que = [start[i]];
        const result = {sum: 0, list: []};
        const dir = [[1, 0], [-1, 0], [0, 1], [0, -1]];
        
        while(que.length){
            const [yP, xP] = que.shift();
            if(arr[yP][xP] === 1) {
                result.sum++;
                result.list.push([yP, xP]);
                arr[yP][xP] = 0;
                for(let j = 0; j < 4; j++){
                    const [ny, nx] = [yP + dir[j][1], xP + dir[j][0]];
                    if(nx >= 0 && ny >= 0 && nx < arr[0].length && ny < arr.length && arr[ny][nx] === 1){
                        que.push([ny, nx]);
                    }
                }
            }
            else if (arr[yP][xP] > 1) continue;
            
            
        }
        // console.log(result)
        result.list.forEach(([yP, xP]) => arr[yP][xP] = result.sum);
        
    }
}


const solution = (land) => {
    const que = [start[i]];
        const result = {sum: 0, list: []};
        const dir = [[1, 0], [-1, 0], [0, 1], [0, -1]];
}

 

그래서 세로줄 별로 탐색을 진행하고, 이미 탐색한 부분은 탐색하지 않게끔 Set객체를 이용해 중복 처리를 진행했다.

코드

const solution = (land) => {
  const que = [];
  const dir = [[-1, 0], [1, 0], [0, -1], [0, 1]];
  const n = land.length;
  const m = land[0].length;
  const vertOil = new Map();
    
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      const oilSet = new Set();
      let oilCnt = 0;
            
      if (land[j][i] === 1) {
        que.push([j, i]);
                
        while (que.length) {
          const [cy, cx] = que.shift();
          if (land[cy][cx] === 1) {
            land[cy][cx] = 0;
            oilCnt += 1;
            if (!oilSet.has(cx)) oilSet.add(cx);
                    
            for (let [dy, dx] of dir) {
              const [ny, nx] = [cy + dy, cx + dx];
              if (ny >= 0 && nx >= 0 && ny < n && nx < m && land[ny][nx] === 1) {
                que.push([ny, nx]);
              }
            }
          }
        }
      }
      if (oilCnt !== 0) {
        for (let x of oilSet) {
          vertOil.set(x, vertOil.has(x) ? vertOil.get(x) + oilCnt : oilCnt);
        }
      }
    }
  }
  return Math.max(...vertOil.values());
}