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

문제 설명

세로 길이가 n, 가로 길이가 m인 격자 모양의 땅 속에 석유가 발견되었습니다. 석유는 여러 덩어리로 나누어져 있으며, 상하좌우로 연결된 석유는 하나의 덩어리로 간주합니다.

조건:

• 시추관은 열 하나를 관통하는 형태로 설치됩니다.
• 열과 열 사이에 시추관을 뚫을 수는 없습니다.
• 시추관이 지나는 석유 덩어리의 크기를 모두 합한 값이 해당 위치에서 뽑을 수 있는 석유량입니다.

주어진 격자 모양의 땅 정보(land)에서 시추관 하나를 설치해 가장 많은 석유를 뽑을 수 있는 위치를 구하세요.

---

제한사항

• 1 ≤ land의 길이 = n ≤ 500
• 1 ≤ land[i]의 길이 = m ≤ 500
• land[i][j]는 0(빈 땅) 또는 1(석유)

---

해결 방법

알고리즘: DFS (깊이 우선 탐색)

1. 석유 덩어리 그룹화
   • DFS를 사용하여 연결된 석유 칸들을 하나의 그룹으로 묶습니다.
   • 각 그룹의 크기를 저장합니다.
2. 열 단위 석유량 계산
   • 각 열을 순회하며 해당 열을 지나는 석유 덩어리들의 크기를 합산합니다.
   • 중복된 석유 덩어리는 제외합니다.
3. 가장 많은 석유량 반환
   • 모든 열에서 석유량을 계산한 후, 가장 큰 값을 반환합니다.

---

시간 복잡도

1. DFS 탐색:
   • 모든 칸을 한 번씩 방문하므로 O(n * m)
2. 열 단위 석유량 계산:
   • 각 열에 대해 행을 탐색하므로 O(n * m)

총 시간 복잡도: O(n * m)

---

구현 코드

function dfs(y, x, group, land) {
  const moveY = [0, 1, 0, -1];
  const moveX = [1, 0, -1, 0];
  let stack = [[y, x]];
  let oilSize = 0;

  while (stack.length > 0) {
    const [curY, curX] = stack.pop();

    if (land[curY][curX] !== 1) {
      continue;
    }

    land[curY][curX] = group;
    ++oilSize;

    for (let i = 0; i < 4; ++i) {
      const nextY = curY + moveY[i];
      const nextX = curX + moveX[i];

      if (isValid(nextY, nextX, land)) {
        stack.push([nextY, nextX]);
      }
    }
  }

  return oilSize;
}

function isValid(y, x, land) {
  return y >= 0 && x >= 0 && y < land.length && x < land[0].length && land[y][x] === 1;
}

function solution(land) {
  let answer = 0;
  let group = 2;
  let groupCnt = [0, 0];

  for (let i = 0; i < land.length; ++i) {
    for (let j = 0; j < land[0].length; ++j) {
      if (land[i][j] === 1) {
        const oilSize = dfs(i, j, group, land);
        groupCnt.push(oilSize);
        ++group;
      }
    }
  }

  for (let i = 0; i < land[0].length; ++i) {
    let visitOilGroup = new Array(group).fill(false);
    let sum = 0;

    for (let j = 0; j < land.length; ++j) {
      const oilNum = land[j][i];
      if (oilNum > 1 && !visitOilGroup[oilNum]) {
        sum += groupCnt[oilNum];
        visitOilGroup[oilNum] = true;
      }
    }

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

  return answer;
}