📌 문제 설명

[PCCP 기출문제] 2번 / 석유 시추 문제 보기

📌 문제 접근

효율성 점수가 있다

그냥 BFS로 전부 찾지 말라는 뜻이라고 인식하였다. 따라서, 미리 한번 다 찾아놓은 다음에 저장하고 가져다 사용하면 된다는 뜻.

bfs 단순 구현 및 land 수치 변경

물론 land를 직접적으로 변경하는 것 보다는 복사하여 변경해야하지만, 혹시나 효율성, 시간 초과 날까봐 원본 수정함. 그리고 visited 만드는 대신 2부터 숫자를 변경하여 최소화하였음.

마지막 겉멋, 메서드 체이닝

그냥 읽기 쉽게 해도 되지만, 간만에 겉멋 좀 내봄. 근데 디버깅 시에는 아찔 할 꺼 같다. 만약 한 번 만에 안맞췄다면 지우고 가독성 좋게 했을 듯하다.

📌 내가 작성한 코드

function solution(land) {
  const [n, m] = [land.length, land[0].length];
  const oil_map = new Map();
  const dx = [0, 0, -1, 1];
  const dy = [-1, 1, 0, 0];
  let oils = 2;
  const bfs = (startX, startY) => {
    const q = [[startX, startY]];
    land[startX][startY] = oils;
    let cnt = 1;
    while (q.length) {
      const [x, y] = q.shift();
      for (let l = 0; l < 4; l++) {
        const nx = x + dx[l];
        const ny = y + dy[l];
        if (0 <= nx && nx < n && 0 <= ny && ny < m && land[nx][ny] === 1) {
          land[nx][ny] = oils;
          cnt++;
          q.push([nx, ny]);
        }
      }
    }
    return cnt;
  };
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      if (land[i][j] === 1) {
        oil_map.set(oils, bfs(i, j));
        oils++;
      }
    }
  }
  return Array.from({ length: m }, (_, j) => j).reduce((acc, _, idx) => {
    acc = Math.max(
      acc,
      [
        ...new Set(
          Array.from({ length: n }, (_, i) => i).map((e) => land[e][idx]),
        ),
      ].reduce((sum, num) => sum + (oil_map.get(num) || 0), 0),
    );
    return acc;
  }, 0);
}

📌 시간 복잡도

• 각 석유 덩어리를 BFS로 탐색하며 번호 매기기: O(n × m)
• 각 열마다 Set을 이용해 중복 제거하고 석유량 합산: O(m × n)
• 전체 시간 복잡도: O(n × m)

📌 참고 링크

• Map

• Array.reduce()

• 너비 우선 탐색(BFS)