코테: Max Area of Island

Yeongjong Kim·2022년 1월 5일

본 문서는 leetcode(https://leetcode.com/problems/max-area-of-island) 문제를 기준으로 작성하였습니다.

Max Area of Island

문제

1은 섬 0은 물을 나타내는 2중 배열(grid)이 주어진다. 이 때 가장 큰 섬의 크기를 반환하는 문제이다.

규칙

m == grid.length
n == grid[i].length
1 <= m, n <= 50
grid[i][j] is either 0 or 1.

문제 풀이 아이디어 생각해보기

Find all number 1 using a double loop statement so that you can find these throughout the grid.
If number 1 is found, use bfs algorithm to count how many number 1 is connnected
Returns the size of the largest island.

풀이

한번 들린 곳은 다시 확인하지 않기 위해 메모이제이션 기법을 사용했다. 그리고 1이 발견되면 bfs 알고리즘으로 섬의 크기 카운팅하는 함수 countConcatenatedNumber1ByBFS를 작성했다.

코드

function maxAreaOfIsland(grid) {
  let result = 0;

  for (let y = 0; y < grid.length; y++) {
    for (let x = 0; x < grid[0].length; x++) {
      if (isVisitedCell(x, y)) continue;

      if (grid[y][x] === 1) {
        result = Math.max(result, countNumber1(x, y));
      }
    }
  }

  function countNumber1(x, y) {
    memo(x, y);

    let result = 1;
    const queue = [[x, y]];

    while (queue.length) {
      const [currentX, currentY] = queue.shift();

      for (const [directionX, directionY] of [[-1, 0], [1, 0], 0, 1], [0, -1]]) {
        const cellValue = grid[currentY + directionY]?.[currentX + directionX];

        if (
          cellValue === undefined ||
          isVisitedCell(currentX + directionX, currentY + directionY)
        )
          continue;

        if (cellValue === 1) {
          queue.push([currentX + directionX, currentY + directionY]);
          memo(currentX + directionX, currentY + directionY);
          result++;
        }
      }
    }

    return result;
  }

  function isVisitedCell(x, y) {
    return grid[y][x] === 2;
  }

  function memo(x, y) {
    grid[y][x] = 2;
  }

  return result;
};

문제점

x와 y를 생각하며 어느 방향으로 이동하는지 생각을 해야한다. 이중 배열의 경우 첫번 째 괄호 접근자에는 y가 입력되어야 하며, 두번 째 괄호 접근자에는 x가 입력되어야 한다.

이러한 사실을 인지하고 모든 함수 혹은 접근자에 y, x를 순서로 사용해야겠다는 기준을 세우는 것도 좋을 것 같다.

위의 코드에서는 함수를 만들었고 함수에서는 x와 y를 순서대로 받아 내부적으로 y, x 순서로 접근자에 입력해 주었다. 이렇게 하면 본인 기준으로 평소에 x, y로 사용하던 습관이 있어서 그런지 조금 더 편리했던 것 같다.

다른 사람의 접근법

다른 사람의 풀이를 2중 포문과 dfs(재귀)로 문제를 풀었다. 성능이 약 2배 차이나는 것을 확인하고 그대로 코드를 복사여 붙여넣기 했는데, 결과를 보니 성능은 별로 차이가 나지 않았다. 서버의 상태에 영향을 받는듯 하다. 그리고 dfs나 bfs나 섬의 크기를 계산하는데 큰 영향을 미친다는 생각이 들지 않는다. 따라서 문제 풀이 방식 보다는 코드의 깔끔함을 보고 배울점을 기록해 보려고 한다.

다른 사람 코드

function maxAreaOfIsland(grid) {
    let res = 0;
    
    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[i].length; j++) {
            if (grid[i][j] === 1) {
                res = Math.max(res, dfs(grid, i, j))
            }
        }
    }
    
    function dfs (grid, i, j)  {
        if (i < 0 || j < 0 || i >= grid.length || j >= grid[i].length || grid[i][j] === 0 ) {

            return 0
        }

        grid[i][j] = 0
        let count = 1;
        count += dfs(grid, i+1, j)
        count += dfs(grid, i-1, j)
        count += dfs(grid, i, j+1)
        count += dfs(grid, i, j-1)
   
        return count;
    }
    
    return res
};

정말 깔끔하다. 내가 푼 풀이를 보면 queue를 사용했기 때문에 dfs 방식에 비해 코드가 길어질 수 밖에 없지만, 코드를 보고 최대한 개선해보기로했다.

코드 개선하기

조건문을 최소화 하자.

깔끔한 코드를 보면 방문한 셀은 0으로 바꿔주고 있다. 본인은 방문한 셀을 2로 설정했는데, 그럴 필요가 없었다. 2중 포문에서는 1을 찾아서 bfs를 진행하기 때문에 방문한 곳을 0으로 설정하면 동일한 섬에 도달하더라도 bfs를 건너 뛸 수 있다.

function memo(x, y) {
  grid[y][x] = 0;
}

for (let i = 0; i < grid.length; i++) {
  for (let j = 0; j < grid[i].length; j++) {
    // if 문을 제거할 수 있다.
    if (grid[i][j] === 1) {
      res = Math.max(res, dfs(grid, i, j))
    }
  }
}

다음으로 isVisitedCell 함수를 수정하면 if문을 최소화 할 수 있다.
우선 1외에 나올 수 있는 값은 undefined(grid 외부) 와 0 뿐이다. 따라서 isPassedTheCell이라고 함수명을 바꾸고 0과 함께 undefined를 체크하여 continue를 해주면 이 조건문을 패스한 값은 무조건 1이 된다.

function isPassTheCell(x, y) {
  return grid[y]?.[x] === undefined || grid[y]?.[x] === 0;
}

for (const [directionX, directionY] of [[-1, 0], [1, 0], 0, 1], [0, -1]]) {
  if (isPassTheCell(currentX + directionX, currentY + directionY))
    continue;

  // if문 제거
  queue.push([currentX + directionX, currentY + directionY]);
  memo(currentX + directionX, currentY + directionY);
  result++;
}

수정 후 최종 코드

function maxAreaOfIsland(grid) {
  let result = 0;

  for (let y = 0; y < grid.length; y++) {
    for (let x = 0; x < grid[0].length; x++) {
      if (grid[y][x] === 1) {
        result = Math.max(result, countNumber1(x, y));
      }
    }
  }

  function countNumber1(x, y) {
    memo(x, y);

    let result = 1;
    const queue = [[x, y]];

    while (queue.length) {
      const [currentX, currentY] = queue.shift();

      for (const [directionX, directionY] of [[-1, 0], [1, 0], 0, 1], [0, -1]]) {
        if (isPassTheCell(currentX + directionX, currentY + directionY))
          continue;

        queue.push([currentX + directionX, currentY + directionY]);
        memo(currentX + directionX, currentY + directionY);
        result++;
      }
    }

    return result;
  }

  function isPassTheCell(x, y) {
    return grid[y]?.[x] === undefined || grid[y]?.[x] === 0;
  }

  function memo(x, y) {
    grid[y][x] = 0;
  }

  return result;
};