Algorithm problem-41

1. 문제

• 0은 물, 1은 땅으로 이루어진 그리드에 이어진 땅이 몇개 존재하는가를 리턴
• 즉, 물로 분단되어진 땅이 몇개인지를 찾는 문제

2. 시도

• 문제를 이해하는건 쉬웠으나, 개념적으로 접근하기가 어렵다
• 이어진 땅을 확인하는 코드를 작성해야 하는데...
• 첫번째, 분단이 되었는지를 확인해야 하는건, 즉 위에 탐색한 1과 같은 행에 1이 존재하는가
• 0열을 탐색하고 1이 있는 행을 체크
• 1열을 탐색할 때, 0열에 1이 있던 행에 1이 없다면 카운트
• 아 그럼 위의 행에 이어진 1은 하나의 덩어리로 봐야하니까 안되겠네..
• 두번째, 0열을 탐색하고 1이 있는 상하좌우에 1이 하나라도 있는지 체크, 없으면 섬이니 카운팅
• 이렇게 풀려면 덩어리인 섬이 체크가 안되겠네...
• 세번째, 1이 있는 위치를 빈 배열에 저장, 인접해있는 좌표는 같은 인덱스에 묶어서 저장
• 즉, 1이 있는 위치를 찾아서 저장하고, 그와 인접해 있는 위치는 배열 내 배열로 하나로 묶어서 저장
• 그 배열의 길이를 리턴하면 덩어리가 계산되게끔
• DFS를 써야 하는 거였구나...

3. 수도 코드

const countIslands = function (grid) {
  // 1의 좌표를 저장해줄 빈 배열 선언
  let sum = [];

  // 그리드의 길이만큼 순회할 예정
  // 그리드의 한 인덱스를 순회하는 중에 1을 만나면 1의 좌표를 배열에 저장
  // 1을 탐색했을 때에, 저장된 좌표에서 인접한 좌표를 찾아 배열 내 배열로 같이 저장
  // 1을 탐색했을 때에, 저장된 좌표와 인접한 좌표가 없으면 배열 내에 새 배열로 저장
  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[i].length; j++) {
      // 이중반복문을 써서 요소를 전부 탐색, 요소가 1인지를 체크
      if (grid[i][j] === '1') {
        // 1이라면, 섬배열에 저장된 좌표와 비교해야 함, 마찬가지로 순회해서 비교
        // 섬배열에 저장할 배열 구조가 문제인데, 배열 내에 섬별로 2중배열을 만들어줄거고
        // 그 2중배열안에 좌표값을 저장해야 하니까, 좌표 또한 배열 구조로 저장해야하나
        // 섬배열에 저장할 구조는 [ [ [i,j] ], [ [k,l] ] ] 구조이니까 2중반복문 순회
        // 문제는 빈 배열일 때, 이것도 if문 처리하면 되긴 할듯
        if (sum.length === 0) { // 섬이 비었다면, 첫 요소이니까 그냥 넣고
          sum.push([[i,j]]);
        } else { // 아니면, 순회시켜서 좌표중 하나라도 겹치는 친구들은 한 인덱스에 몰아 넣고
          for (let k = 0; k < sum.length; k++) {
            for (let l = 0; l < sum[k].length; l++) { 
              break;// 미구현
            }
          }
        }
      }
    }
  }
  // 탐색을 완료한 후 배열의 길이를 리턴
  return sum.length;
};

4. 레퍼런스

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;
    // 카운트한 땅은 0으로 바꾸고, 이어져 있는 섬들도 찾아서 다 물로 바꿔 카운팅되지 않게끔 한다
    grid[row][col] = '0';
    searchIsland(row - 1, col);
    searchIsland(row + 1, col);
    searchIsland(row, col - 1);
    searchIsland(row, col + 1);
  }
  return count;
};