[프로그래머스][PCCP 기출문제] 2번 / 석유 시추 JS풀이

문제 링크

PCCP 2번

 

풀이 방법

정답을 내기 위해 필요한 값들은

1. 모든 석유 덩어리의 크기
2. 시추관을 뚫을 수 있는 열에서 접근 가능한 석유 덩어리의 크기의 합

• 각 열에서 접근 가능한 석유 덩어리의 크기의 합을 저장하기 위해 land의 열의 크기와 같은 1차원 배열(oilArr)을 만듭니다.
• land의 모든 원소를 방문하면서 bfs로 모든 석유 덩어리의 크기를 구합니다.
• 한 덩어리를 구할 때마다 각 col별로 석유 덩어리의 크기를 oilArr에 더해줍니다.

bfs를 사용할 때에는 시간 제한에 걸릴 경우를 대비해서 직접 큐를 구현하는 편입니다

 

1. 내 풀이

class Node {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.front = null;
    this.rear = null;
    this.size = 0;
  }

  enqueue(val) {
    const node = new Node(val);
    if (!this.front) {
      this.front = node;
      this.rear = node;
    } else {
      this.rear.next = node;
      this.rear = node;
    }
    return ++this.size;
  }

  dequeue() {
    if (!this.front) return null;
    const node = this.front;

    if (this.front === this.rear) {
      this.rear = null;
    }

    this.front = this.front.next;
    this.size--;
    return node.val;
  }
}

function solution(land) {
  const COL = land[0].length;
  const ROW = land.length;

  const dr = [0, 0, 1, -1];
  const dc = [1, -1, 0, 0];

  const q = new Queue();

  //시추관을 뚫었을 때 각 컬럼에서 접근 가능한 석유 덩어리의 크기를 저장하기 위한 배열
  const oilArr = new Array(COL).fill(0);

  //모든 배열을 돌면서 석유 덩어리 순회
  for (let r = 0; r < ROW; r++) {
    for (let c = 0; c < COL; c++) {
      //석유가 없는 땅일 경우 다음 칸으로 이동
      if (!land[r][c]) continue;

      //방문한 컬럼을 저장하기 위한 변수
      const visitedCol = new Set();
      //석유 덩어리의 크기를 저장하기 위한 변수
      let oilSize = 0;

      q.enqueue({ currentR: r, currentC: c });
      //방문한 칸은 0으로 수정하여 방문처리
      land[r][c] = 0;
      oilSize++;
      visitedCol.add(c);

      //큐가 빌 때까지 반복
      while (q.size) {
        const { currentR, currentC } = q.dequeue();

        for (let i = 0; i < 4; i++) {
          const nextR = currentR + dr[i];
          const nextC = currentC + dc[i];
          if (
            nextR >= 0 &&
            nextR < ROW &&
            nextC >= 0 &&
            nextC < COL &&
            land[nextR][nextC]
          ) {
            q.enqueue({ currentR: nextR, currentC: nextC });
            land[nextR][nextC] = 0;
            oilSize++;
            visitedCol.add(nextC);
          }
        }
      }

      //덩어리의 크기를 구한 다음, 방문한 컬럼별로 석유 덩어리 크기 oilArr에 더해줌
      Array.from(visitedCol).forEach((c) => {
        oilArr[c] += oilSize;
      });
    }
  }

  return Math.max(...oilArr);
}