JavaScript Algorithm - countIslands

문제설명 : 

세로와 가로의 길이가 각각 R, M인 2차원 R X M 배열 grid가 주어졌을 때, '1'은 땅을 의미하고 '0' 은 물을 의미합니다. 주어진 2차원 배열에 존재하는 섬의 개수를 리턴해야 합니다.

즉,  0은 물이고 1이 땅이니까 1끼리 모여있는 섬의 개수를 리턴하면 됩니다. 그리고 한번 체크한 1에 대해서는 중복해서 체크하지 않는 것도 핵심입니다. 

입력

인자 1 : grid

• 세로와 가로의 길이가 각각 R, M인 2차원 배열
• arr.length는 R
• arr[i].length는 M
• arr[i][j]는 0 또는 1
  
  

출력

• number 타입을 리턴해야 합니다.

주의사항

• 섬이란 물로 둘러싸여 있는 땅을 말합니다.
• 가로 혹은 세로로 땅이 연결되어 있는 경우 하나의 섬으로 간주합니다.
• 2차원 배열의 범위 밖은 물로 둘러싸여 있다고 가정합니다.

입출력 예시

let grid = [
  ['0', '1', '1', '1'],
  ['0', '1', '1', '1'],
  ['1', '1', '0', '0'],
];
let result = countIslands(grid);
console.log(result); // --> 1

grid = [
  ['0', '1', '1', '1', '0'],
  ['0', '1', '0', '0', '0'],
  ['0', '0', '0', '1', '0'],
  ['1', '1', '0', '1', '0'],
  ['1', '1', '0', '1', '0'],
];
result = countIslands(grid);
console.log(result); // --> 3

 

풀이코드 1:

const countIslands = function (grid) {
  // dfs solution
  const HEIGHT = grid.length;
  const WIDTH = HEIGHT && grid[0].length;
  let count = 0;

  for (let row = 0; row < HEIGHT; row++) {
    for (let col = 0; col < WIDTH; col++) {
      if (grid[row][col] === '0') continue;
      count++;
      searchIsland(row, col);
    }
  }

  function searchIsland(row, col) {
    if (row < 0 || col < 0 || row >= HEIGHT || col >= WIDTH) return;
    if (grid[row][col] === '0') return;

    grid[row][col] = '0';
    searchIsland(row - 1, col);
    searchIsland(row + 1, col);
    searchIsland(row, col - 1);
    searchIsland(row, col + 1);
  }

  return count;
};

 

 

풀이코드 2:

function countIslands(grid) {
    // 방문 여부를 체크하기 위한 2차원 배열 생성
    const visited = Array.from(Array(grid.length), () => Array(grid[0].length).fill(false));
    let count = 0;
  
    // 상하좌우 이동을 위한 배열
    const dx = [-1, 1, 0, 0];
    const dy = [0, 0, -1, 1];
  
    // DFS를 위한 함수 정의
    function dfs(x, y) {
      visited[x][y] = true;
  
      // 상하좌우 인접 노드 방문
      for (let i = 0; i < 4; i++) {
        const nx = x + dx[i];
        const ny = y + dy[i];
  
        // 범위를 벗어나거나, 물이라면 방문하지 않음
        if (nx < 0 || ny < 0 || nx >= grid.length || ny >= grid[0].length || grid[nx][ny] === '0') {
          continue;
        }
  
        // 방문하지 않은 인접 노드 방문
        if (!visited[nx][ny]) {
          dfs(nx, ny);
        }
      }
    }
  
    // 모든 노드에 대해서 DFS 실행
    for (let i = 0; i < grid.length; i++) {
      for (let j = 0; j < grid[0].length; j++) {
        if (!visited[i][j] && grid[i][j] === '1') {
          count++;
          dfs(i, j);
        }
      }
    }
  
    return count;
  }