[JS] 석유 시추

 

문제 자체는 정말 어렵다고 느껴질 정도의 난이도는 아니었으나 효율성 부분을 해결하는데 애를 많이 먹은 문제였다.

 

 

문제 자체는 단순하게 접근할 수 있다. 모든 석유덩이의 크기를 미리 계산해둔 후, 세로선마다 석유덩이의 값을 계산해주면 된다.

 

처음에는 dfs를 활용해서 석유덩이의 크기를 계산한 이후 유니온-파인드를 통해서 석유덩이들의 부모노드에 크기를 저장하려 했었다.

 

// 부모노드를 찾는 함수
function getParent(parentArr, i, j) {
  if (parentArr[i][j][0] === i && parentArr[i][j][1] === j) {
    return [i, j];
  }
  parentArr[i][j] = getParent(
    parentArr,
    parentArr[i][j][0],
    parentArr[i][j][1]
  );
  return parentArr[i][j];
}

// 두 부모노드를 합치는 함수
function unionParent(parentArr, [aI, aJ], [bI, bJ]) {
  const a = getParent(parentArr, aI, aJ);
  const b = getParent(parentArr, bI, bJ);
  if (a < b) parentArr[b[0]][b[1]] = a;
  else parentArr[a[0]][a[1]] = b; // 항상 더 작은 값으로
}

function solution(land) {
  const rLen = land.length;
  const cLen = land[0].length;

  const dc = [1, 0, -1, 0];
  const dr = [0, 1, 0, -1];

  const parents = [...Array(rLen)].map((_, i) =>
    [...Array(cLen)].map((_, j) => [i, j])
  );

  const dfs = (r, c, visited) => {
    let ret = 0;
    const stk = [[r, c]];
    while (stk.length) {
      const [r, c] = stk.pop();
      if (visited[r][c]) continue;
      visited[r][c] = true;
      ret += 1;
      for (let d = 0; d < 4; d++) {
        const [nR, nC] = [r + dr[d], c + dc[d]];
        if (
          0 <= nR &&
          nR < rLen &&
          0 <= nC &&
          nC < cLen &&
          !visited[nR][nC] &&
          land[nR][nC] === 1
        ) {
          stk.push([nR, nC]);
          unionParent(parents, [nR, nC], [r, c]);
        }
      }
    }

    return ret;
  };

  const cntAry = [...Array(rLen)].map((_) => Array(cLen).fill(0));

  const visited = [...Array(rLen)].map((_) => Array(cLen).fill(false));
  for (let i = 0; i < rLen; i++) {
    for (let j = 0; j < cLen; j++) {
      if (!visited[i][j] && land[i][j] === 1) {
        const cnt = dfs(i, j, visited);
        const [r, c] = getParent(parents, i, j);
        cntAry[r][c] = cnt;
      }
    }
  }

  let ret = 0;
  for (let i = 0; i < cLen; i++) {
    const visited = [...Array(rLen)].map((_) => Array(cLen).fill(false));
    let tmpSum = 0;
    for (let j = 0; j < rLen; j++) {
      const [r, c] = getParent(parents, j, i);
      if (!visited[r][c]) {
        visited[r][c] = true;
        tmpSum += cntAry[r][c];
      }
    }
    ret = Math.max(ret, tmpSum);
  }
  return ret;
}

 

 

 

 

정확성 테스트는 모두 통과했지만 시간초과 및 런타임 에러가 났다..

 

 

1. 생각해보니 자바스크립트의 재귀 최대호출수는 약 21000번정도이다.. 문제에서 나온 배열의 크기의 최대가 500*500 즉 25000정도이니 런타임 에러가 날만했다. 따라서 dfs를 재귀로 구현한 방법에서 스택을 활용하는 방법으로 바꿔주었다.

 

그럼에도 여전히 시간초과가 났다.

 

2. 시간을 계속 줄이려고 생각한 결과 dfs를 통해 석유덩이의 크기를 구할때, 해당 석유덩이가 어느 열에 포함되어 있는지를 확인하면 굳이 유니온-파인드 알고리즘을 사용하지 않아도 될 것 같았다.

 

따라서 석유덩이를 구하면서 배열에 석유덩이가 포함된 열의 정보를 담아서 해결하려 했는데 이역시 시간초과가 났다.

 

3. 가로줄의 크기가 최대 500이어서 배열의 includes 함수를 사용한 것이 문제인 듯 했다. 따라서 이를 Map자료형으로 바꿔주었더니 해결되었다.

 

function solution(land) {
  const rLen = land.length;
  const cLen = land[0].length;

  const dc = [1, 0, -1, 0];
  const dr = [0, 1, 0, -1];

  const retAry = Array(cLen).fill(0);

  const dfs = (r, c) => {
    let ret = 0;
    const stk = [[r, c]];
    const idxList = new Map();
    while (stk.length) {
      const [r, c] = stk.pop();
      if (!idxList.has(c)) idxList.set(c, true);
      if (visited[r][c]) continue;
      visited[r][c] = true;
      ret += 1;
      for (let d = 0; d < 4; d++) {
        const [nR, nC] = [r + dr[d], c + dc[d]];
        if (
          0 <= nR &&
          nR < rLen &&
          0 <= nC &&
          nC < cLen &&
          !visited[nR][nC] &&
          land[nR][nC] === 1
        ) {
          stk.push([nR, nC]);
        }
      }
    }

    for (const i of idxList) {
      retAry[i[0]] += ret;
    }
  };

  const visited = new Array(rLen).fill().map((_) => new Array(cLen).fill(0));
  for (let i = 0; i < rLen; i++) {
    for (let j = 0; j < cLen; j++) {
      if (!visited[i][j] && land[i][j] === 1) {
        dfs(i, j);
      }
    }
  }

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

 

 

 

4. 블로그 글을 쓰다가 생각나서 해봤는데 어차피 석유덩이가 포함될 수 있는 인덱스는 무조건 붙어야 하므로 범위를 계산하는 식으로 바꿔서 제출했다. 물론 통과는 되었다.

 

시간차이야 Map자료형의 접근 시간복잡도가 (1) 이라 별로 차이나지는 않았다.

 

function solution(land) {
    
    const rLen = land.length
    const cLen = land[0].length
    
    const dc = [1,0,-1,0]
    const dr = [0,1,0,-1]
    
    const retAry = Array(cLen).fill(0)
    
    const dfs = (r,c) => {
        let ret = 0
        const stk = [[r,c]]
        let minC = c
        let maxC = c
        
        while(stk.length){
            const [r,c] = stk.pop()
            minC = Math.min(c,minC)
            maxC = Math.max(c,maxC)
            if(visited[r][c]) continue
            visited[r][c] = true
            ret += 1
            for (let d = 0 ; d < 4 ; d++){
                const [nR,nC] = [r + dr[d] , c + dc[d]]
                if(0<=nR&&nR<rLen&&0<=nC&&nC<cLen&&!visited[nR][nC]&&land[nR][nC]===1){
                    stk.push([nR,nC])
                }
            }
        }
        
        for (let i = minC ; i <= maxC ; i++){
            retAry[i] += ret
        }
    }
    
    
    
    const visited= new Array(rLen).fill().map(_ => new Array(cLen).fill(0));
    for (let i = 0 ; i < rLen ; i++){
        for (let j = 0 ; j < cLen ; j++){
            if(!visited[i][j]&&land[i][j]===1){
                dfs(i,j)
            }
        }
    }
    
    return Math.max(...retAry)
    
}