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

문제

PCCP - 석유 시추

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

 

 

풀이

설명

시추관 하나를 설치해 뽑을 수 있는 가장 많은 석유량을 구하는 문제입니다.

 

매 열마다 행을 하나씩 내려가며 그래프 탐색을 진행해야 합니다.

dfs를 사용할 경우, 재귀 방식을 사용하면 스택 오버플로우가 발생 가능하므로, 비재귀 방식으로 풀어야 합니다.

 

모든 칸에서 그래프 탐색을 진행할 경우, 시간 초과가 발생합니다.

시간을 줄이기 위해서, 한 번 방문한 석유 구역은 번호를 지정한 후, 총량과 방문 기록을 저장하고, 재탐색 대신 미리 저장한 총량을 반환하면 됩니다.

 

예시 코드

function solution(land) {
  const EMPTY = 0;
  const OIL = 1;

  const n = land.length;
  const m = land[0].length;
  let oilIdx = 2;
  const oils = [0, 0];
  const visited = Array.from({ length: n }, () => Array(m).fill(false));
  const dirs = [
    [0, 1],
    [-1, 0],
    [0, -1],
    [1, 0],
  ];
  let answer = 0;

  for (let i = 0; i < m; i++) {
    const visitedOil = new Set();
    let totalOil = 0;

    for (let j = 0; j < n; j++) {
      const tileNum = land[j][i];
      if (tileNum === EMPTY) continue;

      if (tileNum === OIL) {
        const amount = bfs(j, i);
        totalOil += amount;
        oils[oilIdx] = amount;
        visitedOil.add(oilIdx);
        oilIdx++;
      } else {
        if (visitedOil.has(tileNum)) continue;
        visitedOil.add(tileNum);
        totalOil += oils[tileNum];
      }
    }

    answer = Math.max(answer, totalOil);
  }

  return answer;

  function bfs(x, y) {
    let totalOil = 1;
    const queue = new Queue();
    queue.enqueue([x, y]);
    visited[x][y] = true;

    while (!queue.isEmpty()) {
      const [cx, cy] = queue.dequeue();
      land[cx][cy] = oilIdx;

      for (const [dx, dy] of dirs) {
        const nx = cx + dx;
        const ny = cy + dy;

        if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
        if (visited[nx][ny]) continue;
        if (land[nx][ny] === EMPTY) continue;

        visited[nx][ny] = true;
        totalOil += 1;
        queue.enqueue([nx, ny]);
      }
    }

    return totalOil;
  }
}