[Graph][Medium] 200. Number of Islands

 

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

 

Q. grid가 주어질 때, 섬으로 구분되어 질 수 있는 1 영역의 수를 구하라. 

 

 

Solution. 

  그래프 관련 문제는 노드 방문을 어떤 방식으로 하고, 관련 처리를 어떻게 할지 등이 대부분이다. 

  이 문제에서는 모든 cell이 노드 진입로가 될 수 있다. 한번 진입하면 해당 진입 노드로 갈 수 있는 영역은 모두 방문처리 해 주고,  최종 몇 회 진입 할 수 있는지 찾는 문제다. 

 

 이 경우 방문은 DFS, BFS 모두 유효하다.

 재 방문 하지 않도록 flag처리를 잘 하자.

 

 

void BFS(vector<vector<char>>& grid, int ix, int iy, vector<bool>& vVisit)
{
    int H = grid.size();
    int W = grid[0].size();
    int idx = iy*W + ix;

    queue<int> qBuff;
    qBuff.push(idx);
    while(qBuff.size() > 0)
    {
        int idx = qBuff.front();
        qBuff.pop();
        if(vVisit[idx]) continue;

        vVisit[idx] = true;
        int y = idx / W;
        int x = idx % W;

        // up
        if(y>0 && grid[y-1][x]=='1')    qBuff.push(idx-W);

        // down
        if(y<H-1 && grid[y+1][x]=='1')  qBuff.push(idx+W);

        // left
        if(x>0 && grid[y][x-1]=='1')    qBuff.push(idx-1);

        // right
        if(x<W-1 && grid[y][x+1]=='1')  qBuff.push(idx+1);
    }
}

int numIslands(vector<vector<char>>& grid) 
{
    int H = grid.size();
    int W = grid[0].size();

    int count = 0;
    vector<bool> vVisit;
    vVisit.resize(H*W, false);
    for(int y = 0; y < H; ++y)
    {
        for(int x = 0; x < W; ++x)
        {
            int idx = y*W + x;
            if(grid[y][x] == '1' && !vVisit[idx])
            {
                ++count;
                BFS(grid, x, y, vVisit);
            }
        }
    }
    return count;
}

 

방문 방법, 버퍼 선택 등에 의해 속도차이는 대동소이 하게 발생한다.