PCCP 기출 문제 2번 석유 시추 (js)

석유 시추 (180) 문제 보러 가기

---

문제 조건

• 세로길이가 n 가로길이가 m인 격자
• 석유는 여러 덩어리
• 수직으로 단 하나만 뚫을 수 있을 때 많은 석유를 뽑을 수 있는 시추관의 위치 찾기
• 시추관이 석유 덩어리의 일부를 지나면 해당 덩어리에 속한 모든 석유를 뽑을 수 있습니다.

---

문제 풀이(1) 효율성 실패

function solution(land) {
  const n = land[0].length; // 세로 n
  const m = land.length; // 가로 m

  const tries = Array(n).fill(0);
  let count = 0;

  for (let j = 0; j < n; j++) {
    const currentLand = JSON.parse(JSON.stringify(land));
    for (let i = 0; i < m; i++) {
      if (currentLand[i][j] === 1) {
        drill(currentLand, i, j);
      }
      tries[j] = count;
    }
    count = 0;
  }

  function drill(tryLand, i, j) {
    tryLand[i][j] = 0;
    count++;

    if (i - 1 >= 0 && tryLand[i - 1][j] === 1) drill(tryLand, i - 1, j);
    if (i + 1 < m && tryLand[i + 1][j] === 1) drill(tryLand, i + 1, j);
    if (j - 1 >= 0 && tryLand[i][j - 1] === 1) drill(tryLand, i, j - 1);
    if (j + 1 < n && tryLand[i][j + 1] === 1) drill(tryLand, i, j + 1);
  }

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

1. 하나의 column에서 추출할 수 있는 모든 석유를 추출한 값을 저장한다.

2. 석유를 복원한다.

3. 모든 column에 대해 시행한다.

 

석유를 매 시행마다 복원한 이유는 최종 결과를 훼손하지 않기 위함이었다.

 

효율성에서 당연히 실패할 거라는 것을 알지만 우선 이 방식이 잘 작동하는지 체크하기 위함이었다.

---

문제 풀이(2) 효율성 5에서 실패

function solution(land) {
  const n = land[0].length; // 세로 n
  const m = land.length; // 가로 m

  const oils = Array(n).fill(0);
  const visited = Array(m)
    .fill()
    .map((_) => Array(n).fill(false));
  let volume = 0;
  let startY = 0;
  let finishY = 0;

  for (let j = 0; j < n; j++) {
    startY = j;

    for (let i = 0; i < m; i++) {
      // 방문하지 않은 영역의 석유 덩어리의 크기 구하기
      if (land[i][j] === 1 && !visited[i][j]) {
        drill(land, i, j);
      }

      // 석유 덩어리가 포함하는 모든 Y좌표에 해당 크기를 저장
      for (let k = startY; k <= finishY; k++) {
        oils[k] += volume;
      }
      finishY = 0;
      volume = 0;
    }
  }

  function drill(visited, i, j) {
    visited[i][j] = true;
    volume++;
    finishY = Math.max(finishY, j);

    if (i - 1 >= 0 && visited[i - 1][j] === 1) drill(visited, i - 1, j);
    if (i + 1 < m && visited[i + 1][j] === 1) drill(visited, i + 1, j);
    if (j - 1 >= 0 && visited[i][j - 1] === 1) drill(visited, i, j - 1);
    if (j + 1 < n && visited[i][j + 1] === 1) drill(visited, i, j + 1);
  }

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

1. 한 번 구한 석유 덩어리는 방문처리하여 다시 구하지 않도록 한다.

2. 석유 덩어리의 시작 x좌표와 끝 x좌표에 석유 덩어리 값을 저장한다.

 

이번에는 이미 구한 석유 덩어리를 복원하지 않고,

해당 덩어리를 지나가는 시추공에 미리 값을 더해주었다.

 

1번 시추공이 지날 때 마주친 석유 덩어리의 크기를

1,2,3 시추공 모두에 더해준다.

[8, 8, 8, 0, 0, 0, 0, 0]

 

4번 시추공도 마찬가지로 지나가며

4,5,6,7 시추공이 구할 값에 모두 더해준다

[8, 8, 8, 7, 7, 7, 7, 0]

그리고 7번 시추공은

7,8 시추공에 값을 더해준다.

[8, 8, 8, 7, 7, 7, 7+2, 2]

 

아무튼 이렇게 했지만, 재귀로 구현했다보니 stack overflow 에러가 난 듯하다.

재귀는 항상 위험이 도사린다. 무섭다 무서워

---

문제풀이 (3) 성공

function solution(land) {
  const n = land[0].length; // 세로 n
  const m = land.length; // 가로 m

  const oils = Array(n).fill(0);
  const visited = Array(m)
    .fill()
    .map((_) => Array(n).fill(false));

  const queue = [];
  const directions = [
    [-1, 0],
    [1, 0],
    [0, -1],
    [0, 1],
  ];

  for (let j = 0; j < n; j++) {
    for (let i = 0; i < m; i++) {
      if (land[i][j] === 1 && !visited[i][j]) {
        let volume = 0;
        let startY = j;
        let finishY = 0;

        queue.push([i, j]);
        visited[i][j] = true;

        while (queue.length) {
          const [x, y] = queue.shift();
          volume++;
          finishY = Math.max(finishY, y);

          for (const [dx, dy] of directions) {
            const nx = x + dx;
            const ny = y + dy;
            const isInGrid = nx >= 0 && nx < m && ny >= 0 && ny < n;
            const canDrill = isInGrid && !visited[nx][ny] && land[nx][ny] === 1;

            if (canDrill) {
              queue.push([nx, ny]);
              visited[nx][ny] = true;
            }
          }
        }

        for (let k = startY; k <= finishY; k++) {
          oils[k] += volume;
        }
      }
    }
  }

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

1. stack overflow 에러가 나지 않도록 queue를 이용하여 bfs 방식으로 구현했다.

---

후기

1. 500*500 케이스여서 효율성을 신경쓰지 않고 내가 편한대로 재귀로 풀었다.
2. 그리고 효율성을 두 번 탈락하고 나서 bfs로 해야겠다는 생각이 뒤늦게 들었다.
3. 앞으로는 최선의 방법을 못 찾았을 때만, 고육지책으로 편한 방법을 시도해야겠다
4. queue로 구현하는 연습을 해야겠다.