[Algorithm] [알고리즘] Depth First Search

😅 DFS가 뭐야!

: Depth First Search
: parents 노드부터 가장 깊은 child 노드까지 탐색을 하는 방법 (차례 차례 쭉쭉 내려가자)
: 재귀함수의 연속 호출이나 스택으로 구현되고 있다

✍️ 오늘 다루어볼 문제는!!

1로 이루어진 덩어리? 묶음?이 총 몇개 인지 찾는 문제이다!!

const input = [
  ["1", "1", "1", "1", "1"],
  ["1", "1", "1", "1", "0"],
  ["1", "1", "0", "0", "0"],
  ["0", "0", "1", "1", "0"],
  ["0", "0", "0", "0", "0"],
  ["0", "1", "0", "0", "0"],
  ["0", "0", "0", "1", "1"],
  ["1", "0", "0", "1", "1"],
  ["1", "0", "0", "0", "0"],
  ["1", "1", "0", "0", "0"],
];

// input : 2D Array

function main(grid) {
  // N x M matrix
  let numOfIsland = 0; // 묶음의 개수
  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[0].length; j++) {
      if (grid[i][j] === "1") { 
        dfs(grid, i, j);
        numOfIsland++;
        console.log(grid);
      }
    }
  }
  console.log(numOfIsland);
}

// recursion
function dfs(grid, i, j) {
  // end clause
  if (
    i < 0 ||
    i >= grid.length ||
    j < 0 ||
    j >= grid[0].length ||
    grid[i][j] === "0"
  )
    return;

  grid[i][j] = "0"; // 지나간 자리를 0으로 바꾸어줌
  const direction = [
    [-1, 0], // 상
    [0, 1], // 우
    [1, 0], // 하
    [0, -1], // 좌
  ];

  for (let d = 0; d < direction.length; d++) {
    const newI = direction[d][0] + i;
    const newJ = direction[d][1] + j;
    dfs(grid, newI, newJ);
  }
  return;
}

main(input);

-> 상우하좌 순으로 탐색하여 1을 0으로 바꾸어줌

재귀 ,, 너무 어렵다 ,,