[LeetCode] BFS-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.

 

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'.

---

문제풀이

이렇게 있다고 가정해보자

const grid = [
    ['1', '1', '1'],
    ['1', '0', '1'],
    ['1', '0', '1'],
]

 

1. 먼저 처음 시작할 좌표를 구한다 => row = 0, col = 0

2. 모든 row, col을 순회하기 위해 width에 해당하는 for, height에 해당하는 for을 만든다

for(let row = 0; row < height; row++) {
	for(let col = 0; col < width; col++) {
    	...
    }
}

3. grid[row][col] = 1일 때만 섬을 구하는 카운트 다운을 한다

for(let row = 0; row < height; row++) {
    for(let col = 0; col < width; col++) {
    	if(grid[row][col] === 1) {
        	...
        }
    }
}

4. 1번과 2번을 만족할 경우 => 위, 아래, 왼쪽, 오른쪽을 모두 순회하는 함수를 만들자 => traverse로 짓는다.

traverse 함수 중 

- traverse를 중단하는 조건을 만든다

function traverse(r, c) {
    if(r < 0 || c < 0 || r >= height || c >= width || grid[r][c] === '0') {
        return ;
    }
}

- 현재 grid[row][col]는 1일 경우 => 0으로 바꾼다

function traverse(r, c) {
    if(r < 0 || c < 0 || r >= height || c >= width || grid[r][c] === '0') {
        return ;
    }
    
    grid[row][col] = 0
}

 

이런 grid가 있다고 가정하자

const grid = [
    ['1', '1', '1'],
    ['1', '0', '1'],
    ['1', '0', '1'],
]

 

DFS로 풀 때

[1] grid[0][0] === 1이기 때문에 grid[0][0] === 0으로 변경

[2] (grid[0][0]의 윗 방향) grid[- 1][0]은 1이 아니기 때문에 함수 종료

 

[3] (grid[0][0]의 아래 방향) grid[1][0]은 1이기 때문에 grid[1][0] === 0으로 변경

[4] grid[1][0]에서 다시 '위 아래 왼쪽 오른쪽' 시작

[5] (grid[1][0]의 윗 방향) grid[0][0]은 0이기 때문에 함수 종료

[6] (grid[1][0]의 아랫방향) grid[2][0]은 1이기 때문에 === 0으로 변경

[7] grid[2][0]에서 다시 '위 아래 왼쪽 오른쪽' 시작

...

 

grid[2][0]의 위 아래 왼쪽 오른쪽의 작업이 다 끝나면 다시

grid[1][0]의 왼쪽 ([6] 이후의 태스크)를 시작

...

 

function traverse(r, c) {
    if(r < 0 || c < 0 || r >= height || c >= width || grid[r][c] === '0') return;
    grid[r][c] = '0';
    traverse(r - 1, c);
    traverse(r + 1, c);
    traverse(r, c - 1);
    traverse(r, c + 1);
}

- count를 리턴한다

 

---

코드

 

DFS로 풀기

- grid[r][c] === 1 인 경우, grid[r][c] 기준으로 윗, 아래, 왼쪽, 오른쪽을 돌고

- 예를 들어 윗쪽으로 갔을 때 0으로 확인된다면 grid[r][c] 기준으로 아래로 traverse

- 하지만 윗쪽으로 갔을 때 1로 확인된다면, grid[r+1][c] 기준으로 다시 윗, 아래, 왼쪽, 오른쪽을 돈다

// DFS

var numIslands = function(grid) {
    if (grid.length <= 0) return 0;
    let count = 0, DIRECTIONS = [[-1,0],[0,1],[1,0],[0,-1]];
    let height = grid.length, width = grid[0].length;
    for (let row = 0; row < height; row++) {
        for (let col = 0; col < width; col++) {
            if (grid[row][col] == '1') { // there is no chance '0' is part of an island
                traverse(row, col); // once this finishes, we've visited all lands of one island
                count++;
            }
        }
    }

    return count;
    
    // DFS Traversal
    function traverse(row, col) {
        if (row < 0 || row >= height || col < 0 || 
            col >= width || grid[row][col] == '0') {
            return;
        }
        grid[row][col] = "0"; // turn land to water since we already visited it
        for (let dir of DIRECTIONS) {
            traverse(row+dir[0],col+dir[1]);
        }
    }
    // Time Complexity: O(m*n)
    // Space Complexity: O(m*n), if the entire grid is one island, it will take up m*n space in function call stack
};

 

BFS로 풀기

- grid[r][c] === 1 일 경우에, grid[r][c] 기준으로 윗, 아래, 왼쪽, 오른쪽을 돈다

- 만약 윗쪽이 0이라도, DFS와 다르게 grid[r][c]의 아래, 왼쪽, 오른쪽을 다 돌고 그다음 grid[r+1][c]로 이동해서 윗 아래 왼쪽 오른쪽을 돈다.

- 만약 윗쪽이 1일 경우에 => grid[r+1][c] 기준으로 윗, 아래, 왼쪽, 오른쪽 기준의 [row, col] 배열들을 뒤에 넣어서 grid[r][c]의 윗, 아래, 왼쪽, 오른쪽이 모두 끝난 후에야 traverse 할 수 있도록 한다

// BFS

var numIslands = function(grid) {
    let height = grid.length, width = grid[0].length;
    let count = 0;
    const DIRECTIONS = [[-1,0],[0,1],[1,0],[0,-1]];
    for (let row = 0; row < height; row++) {
        for (let col = 0; col < width; col++) {
            if (grid[row][col] == "1") {
                count++;
                traverse([[row,col]]);
            }
        }
    }
    return count;
    
    // BFS Traversal
    function traverse(queue) {
        while (queue.length > 0) {
            let [row, col] = queue.shift();
            if (row < 0 || row >= height || col < 0 || col >= width 
                || grid[row][col] == '0') continue;
            grid[row][col] = "0"; // mark so that we know we already visited it
            for (let dir of DIRECTIONS) {
                queue.push([row+dir[0], col+dir[1]]);
            }
        }
    }
    // Time Complexity: O(m*n)
    // Space Complexity: O(m*n), queue might contain m*n elements if the entire grid is one island
};