[LeetCode][Graph] Number of Islands 풀어보기

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

Number of Islands - LeetCode

유명한 형태의 2차원 그래프 문제입니다.

가장 간단하게 bfs혹은 dfs를 통해서 해결할 수 있습니다.

 

저는 익숙한 bfs를 사용했는데, vector기반의 dfs를 사용하는 것이 성능상으로는 더 이점을 가질 수도 있겠습니다.

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        N = grid.size();
        M = grid[0].size();
        int answer = 0;
        for (int i = 0; i < N; ++i)
        {
            for (int j = 0; j < M; ++j)
            {
                if (grid[i][j] == '1')
                {
                    bfs(i, j, grid);
                    ++answer;
                }
            }
        }
        return answer;
    }

    void bfs(int sr, int sc, vector<vector<char>>& grid)
    {
        queue<pair<int, int>> q;
        q.push({ sr, sc });
        grid[sr][sc] = '0';

        while (!q.empty())
        {
            auto [r, c] = q.front();
            q.pop();
            for (int i = 0; i < 4; ++i)
            {
                int nr = r + dr[i];
                int nc = c + dc[i];

                if (nr >= 0 && nr < N && nc >= 0 && nc < M &&
                    grid[nr][nc] == '1')
                {
                    grid[nr][nc] = '0';
                    q.push({ nr, nc });
                }
            }
        }
    }

public:
    int dr[4] = { -1, 0, 1, 0 };
    int dc[4] = { 0, -1, 0, 1 };
    int N, M;
};

해당 문제는 알고리즘 자체보다는 미세 최적화 요소만 있어서 별도의 다른 방법은 적지 않겠습니다.