[Toy Problem] countIslands

문제

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

입력

인자 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. input변수 grid를 탐색하며 '1'(땅)이 시작되면 visit모듈을 시작한다.
2. visit모듈 실행 중 땅일경우 방문했다는 표시를 한다.
3. 상하좌우 중 상은 반복문에서 탐색중이므로 상을 뺸 탐색을 실시하여 모든 땅을 탐색한다.
4. visit모듈이 끝나면 섬 하나가 있으므로 answer++
5. 반복문에서 같은땅을 탐색하더라도 '1'이 아닌 true로 바뀌어 있으므로 다시 탐색할 일은 없다.
6. 반복문 탐색이 끝난 후 answer(섬의 갯수)를 리턴.

Solution

const countIslands = function (grid) {
  if (!grid.length) return 0
  let R = grid.length;
  let C = grid[0].length
  let answer = 0

  const visit = (r, c) => {
    if (r < 0 || r >= R || c < 0 || c >= C) return
    if (grid[r][c] === '0' || grid[r][c] === true) return
    grid[r][c] = true
    visit(r + 1, c)
    visit(r, c + 1)
    visit(r, c - 1)
  }
  for (let i = 0; i < R; i++) {
    for (let j = 0; j < C; j++) {
      if (grid[i][j] === '1') {
        visit(i, j)
        answer++
      }
    }
  }
  return answer
};

GItHub repo