[LeetCode] 200 - Number of Islands

문제

• 링크: https://leetcode.com/problems/number-of-islands
• 난이도: Medium
• 태그: 배열, 깊이 우선 탐색, 너비 우선 탐색, 행렬
• 결과: Time: 11 ms (99.99%), Space: 23.37 MB (25.04%)

풀이

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int r = grid.size();
        int c = grid[0].size();
        
        int cnt = 0;
        for (int i = 0; i < r; ++i)
        {
            for (int j = 0; j < c; ++j)
            {
                if (grid[i][j] == '0')
                {
                    continue;
                }

                cnt++;
                queue<pair<int, int>> q;
                q.push({i, j});
                grid[i][j] = '0';
        
                while (!q.empty())
                {
                    int x, y;
                    tie(x, y) = q.front();
                    q.pop();
    
                    int dx[] = { 0, 1, 0, -1 };
                    int dy[] = { 1, 0, -1, 0 };

                    for (int dir = 0; dir < 4; ++dir)
                    {
                        int nx = x + dx[dir];
                        int ny = y + dy[dir];

                        if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
                        if (grid[nx][ny] == '0') continue;

                        grid[nx][ny] = '0';
                        q.push({nx, ny});
                    }
                }
            }
        }

        return cnt;
    }
};

배운 점과 후기

간단한 BFS로 풀었다.

이 포스트는 달레 스터디(7주차)에서 진행한 Blind 75 문제집 풀이의 일부입니다.