[LeetCode] 200. Number of Islands

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

LeetCode - Number of Islands

문제 유형 : dfs/bfs, 행렬

문제 난이도 : Medium

 

문제

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 크기의 2차원 배열 grid가 있다.

땅은'1', 물은 '0'으로 표시된다.

섬의 개수를 반환하시오. 섬은 물로 감싸져있고 인접한 땅으로 연결될 수 있습니다.

grid배열의 밖은 전부 물이라 생각하시오.

 

풀이

너무 대표적인 그리드 탐색 문제이다.

 

방문 정보를 담기 위해 grid와 같은 크기의 bool 행렬을 만들고, 2차원배열을 순차적으로 읽으면서, 땅을 발견하고, 방문한 적이 없다면, 그 자리에서 카운트를 1 올리고 인접한 노드들을 dfs/bfs해주면 된다.

 

최종적으로 섬의 카운트를 반환해주면 된다.

 

코드

C++

코드가 지저분해보인다면, 탐색은 따로 나눠도 된다.

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        int ans = 0;
        int di[] = {1, -1, 0, 0};
        int dj[] = {0, 0, 1, -1};

        vector<vector<bool>> visited(n, vector<bool>(m, false));
        queue<pair<int, int>> q;

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(grid[i][j] == '1' && !visited[i][j]) {
                    ans++;
                    q.push({i, j});
                    visited[i][j] = true;

                    while(!q.empty()) {
                        auto curr = q.front();
                        q.pop();

                        for(int k = 0; k < 4; k++) {
                            int ni = curr.first + di[k];
                            int nj = curr.second + dj[k];

                            if(ni >= 0 && ni < n && nj >= 0 && nj < m && grid[ni][nj] == '1' && !visited[ni][nj]) {
                                q.push({ni, nj});
                                visited[ni][nj] = true;
                            }
                        }
                    }
                }
            }
        }

        return ans;
    }
};

 

Go

func numIslands(grid [][]byte) int {
	n := len(grid)
	m := len(grid[0])
	ans := 0
	di := []int{1, -1, 0, 0}
	dj := []int{0, 0, 1, -1}

	visited := make([][]bool, n)
	for i := range visited {
		visited[i] = make([]bool, m)
	}

	q := make([][2]int, 0)

	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if grid[i][j] == '1' && !visited[i][j] {
				ans++
				q = append(q, [2]int{i, j})
				visited[i][j] = true

				for len(q) > 0 {
					curr := q[0]
					q = q[1:]

					for k := 0; k < 4; k++ {
						ni := curr[0] + di[k]
						nj := curr[1] + dj[k]

						if ni >= 0 && ni < n && nj >= 0 && nj < m && grid[ni][nj] == '1' && !visited[ni][nj] {
							q = append(q, [2]int{ni, nj})
							visited[ni][nj] = true
						}
					}
				}
			}
		}
	}

	return ans
}