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

문제

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

풀이

• 가장 많은 석유를 지나치는 컬럼을 찾고 그 석유 수를 반환하며 된다
• 섬 개수 세기의 변형 문제. 최대 개수를 세는 문제이므로 dfs
• 컬럼을 기준으로 석유를 세면 중복이 발생한다.
  • 1번, 2번, 3번 컬럼은 동일하게 9개임
  • 중복으로 dfs 하게 되면 시간초과남
• visited 배열을 만들어서 dfs 돌 때마다 석유가 있는 컬럼를 기록한다.
  • 중복을 피하기 위해 land의 값에 직접 방문여부를 표시하게 되면 매 dfs 마다 land를 초기화해야 해서 시간초과남
  • dp 배열을 만들어서 dfs 돌 때마다 visited에 각 컬럼마다 석유 수를 업데트 해준다

코드

function solution(land) {
  let dx = [-1, 0, 1, 0];
  let dy = [0, 1, 0, -1];
  const n = land.length;
  const m = land[0].length;
  let answer = 0;
  let dp = Array.from({ length: m }).fill(0);
  let visited = Array.from({ length: m }).fill(0);

  const dfs = (y, x, visited, cnt) => {
    land[y][x] = 0;
    visited[x] = 1;
    for (let k = 0; k < 4; k++) {
      let nx = x + dx[k];
      let ny = y + dy[k];
      if (nx >= 0 && nx < m && ny >= 0 && ny < n && land[ny][nx] === 1) {
        cnt += dfs(ny, nx, visited, cnt);
      }
    }

    for (let l = 0; l < visited.length; l++) {
      if (visited[l]) {
        dp[l] += cnt;
      }
    }
    cnt = 0;
    return cnt;
  };

  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (land[j][i] === 1) {
        visited = Array.from({ length: m }).fill(0);
        dfs(j, i, visited, 1);
      }
    }
  }

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

정리

• 거의 반나절 걸렸던 거 같다. 처음엔 단순하게 dfs로 각 컬럼 기준으로 석유를 셌다가 중복이 발생해서 시간초과.
• bfs로 해봐도 동일해서 매 순회마다 land를 초기화 해야하는 것이 시간초과 원인임을 알게 됨
• land를 초기화 안 하고 하는 방법을 한참 찾았다.
• visited로 컬럼을 기록하는 것까지는 떠올렸는데 누적합(맞는 용어인지 모르겠지만)으로 매번 업데이트 해주는 것까지는 도저히 생각이 안나 [질문하기]에서 힌트를 얻어 해결
• PCCP 설레는 친구다..