섬의 개수 - 4963번 백준

문제

문제 난이도: 실버 2

문제 분류: BFS 혹은 DFS

 

문제 풀이 및 코드

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;

vector<vector<bool>> Visited;
vector<vector<bool>> Map;

int LandNum()
{
    queue<pair<int, int>> q;
    for (int h = 0; h < Map.size(); ++h)
    {
        for (int w = 0; w < Map[h].size(); ++w)
        {
            if (Map[h][w] == true)
            {
                q.push({ h, w });
            }
        }
    }
    int Count = 0;
    while (!q.empty())
    {
        pair<int, int> p = q.front();
        q.pop();
        if (Visited[p.first][p.second] == true) continue;

        queue<pair<int, int>> qq;
        qq.push({ p.first ,p.second });
        
        while (!qq.empty())
        {
            pair<int, int> pp = qq.front();
            qq.pop();
            if (Visited[pp.first][pp.second] == true) continue;
            Visited[pp.first][pp.second] = true;

            if (pp.first > 0)
            {
                qq.push({ pp.first - 1 , pp.second });
            }
            if (pp.first < Map.size() - 1)
            {
                qq.push({ pp.first + 1 , pp.second });
            }
            if (pp.second > 0)
            {
                qq.push({ pp.first  , pp.second - 1 });
            }
            if (pp.second < Map[0].size() - 1)
            {
                qq.push({ pp.first , pp.second + 1 });
            }

            if (pp.second > 0 && pp.first > 0)
            {
                qq.push({ pp.first - 1, pp.second - 1 });
            }

            if (pp.second < Map[0].size() - 1 && pp.first > 0)
            {
                qq.push({ pp.first - 1, pp.second + 1 });
            }

            if (pp.second > 0 && pp.first < Map.size() - 1)
            {
                qq.push({ pp.first + 1, pp.second - 1 });
            }

            if (pp.second <  Map[0].size() - 1 && pp.first < Map.size() - 1)
            {
                qq.push({ pp.first + 1, pp.second + 1 });
            }

        }
        Count++;
    }
    return Count;
}

void Init()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

int main()
{
    //Initialize
    Init();
    //Input
    vector<int> AnswerVec;
    while (true)
    {
        int w, h = 0;
        cin >> w >> h;
        if (w == 0 && h == 0)
        {
            break;
        }
        else
        {
            vector<vector<bool>> ThisMap(h, vector<bool>(w, false));
            vector<vector<bool>> ThisVisited(h, vector<bool>(w, false));

            for (int i = 0; i < h; i++)
            {
                for (int j = 0; j < w; j++)
                {
                    bool Tmp;
                    cin >> Tmp;
                    ThisMap[i][j] = Tmp;
                    ThisVisited[i][j] = !Tmp;
                }
            }
            


            Map = ThisMap;
            Visited = ThisVisited;
            

            AnswerVec.push_back(LandNum());
        }
    }

    for (int i : AnswerVec)
    {
        cout << i << "\n";
    }

}