LeetCode Number of Islands (JavaScript), DFS

링크 : https://leetcode.com/problems/number-of-islands/description/

문제 설명

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

Example 2:

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] is '0' or '1'.

---

문제 풀이

dfs를 이용하여 접근

- 2중 for문을 돌며 '1'인 위치에 dfs를 검사 및 answer 1증가 -> 이어진 경로 탐색하기 위해

- dfs 함수 : 상, 하, 좌, 우 기준 연결된 모든 지역 검사 및 지나온 구역 '0'으로 초기화

- 최종적으로 answer 리턴

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function(grid) {
    let answer = 0;
    let direction = [
        [0, 1],
        [1, 0],
        [-1, 0],
        [0, -1]
    ];
    
    function dfs(y, x) {
        grid[y][x] = '0';

        for (const [dx, dy] of direction) {
            const mx = x + dx;
            const my = y + dy;

            if (
                mx >= 0 && mx < grid[0].length && 
                my >= 0 && my < grid.length &&
                grid[my][mx] === '1'
            ) {
                dfs(my, mx);
            }
        }
    }

    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[0].length; j++) {
            if (grid[i][j] === '1') {
                dfs(i, j);
                answer++;
            }
        }
    }

    return answer;
};

---

결론

기본적인 dfs 문제