[dfs] 200번 Number of Islands

문제

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.

m x n 2D 이진 grid가 '1'(육지) 및 '0'(물) 지도를 나타낼 때, 섬 수를 반환합니다.

섬은 물로 둘러싸여 있고 인접한 육지를 수평 또는 수직으로 연결하여 형성됩니다. grid의 네 모서리가 모두 물로 둘러싸여 있다고 가정할 수 있습니다.

예시

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

제약

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

코드

const numIslands = (grid) => {
    const m = grid.length
    const n = grid[0].length
    let res = 0;

    const dfs = (x, y) => {
        if (x < 0 || x > m - 1 || y < 0 || y > n - 1) return
        
        if (grid[x][y] === '1') {
            grid[x][y] = 'visited';
            
            dfs(x - 1, y);
            dfs(x, y - 1);
            dfs(x + 1, y);
            dfs(x, y + 1);
            return true;
        }
        return false
    }
    
    [...Array(m).keys()].forEach(i => {
         [...Array(n).keys()].forEach(j => {
             if (dfs(i, j) === true) res += 1
         })
    })
    
    return res;
};

풀이

• 특정 노드에 방문했을 때 해당 노드가 '1'이면 방문처리(visited)를 하고 해당 노드의 상, 하, 좌, 우를 방문한다.
  • 첫 방문에 성공했으면 true를 리턴하고 방문에 싪패하면 false를 리턴한다.
  • 잘못된 인덱스면 곧 바로 종료한다.
  • 첫 방문에 성공하면 그 주변에에 방문 가능한 곳을 모두 방문하여 방문처리를 해버리는 것이다.
• 모든 노드를 탐색해가며 첫 방문 성공일때(true) 를 카운트한다.