백준 4963번 - 섬의 개수 (C++)

문제

해결 방법

Dfs방식을 사용하여 세계 전체를 순환하다가, 땅을 찾는다면 해당 땅을 기준으로 주변 탐색-> 땅을 탐색했다면 탐색된 땅의 주변 검색 -> 을 반복하며 연결된 땅을 모두 검색한다.

 

아쉬웠던 점

[주변칸 탐색 -> 땅이라면 또 주변칸 탐색 -> 반복]으로 구성되어있어, 이전에 검색했던 범위는 반복을 하지 않는 방법이 있나 생각해보았는데 잘 모르겠다. 

 

코드

#include <iostream>
#include <vector>
using namespace std;
 
struct Island
{
    int Type;
    bool Check = false;
};
 
void Find_Island(vector<vector<Island>> &_Vec, int _y, int _x)
{
    _Vec[_y][_x].Check = true;
 
    for(int i = _y - 1; i <= _y + 1; ++i)
        for (int j = _x - 1; j <= _x + 1; ++j)
        {
            if (i >= _Vec.size() || i < 0 || j >= _Vec[i].size() || j < 0)
                continue;
            if (!_Vec[i][j].Check && _Vec[i][j].Type == 1)
                Find_Island(_Vec, i, j);
        }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    while (true)
    {
        int w, h, ans = 0;
        cin >> w >> h;
        if (w == 0 && h == 0)
            break;
        
        vector<vector<Island>> VecMap(h);
        for (int i = 0; i < h; ++i)
            for (int j = 0; j < w; ++j)
            {
                VecMap[i].emplace_back();
                cin >> VecMap[i][j].Type;
            }
 
        for (int i = 0; i < h; ++i)
            for (int j = 0; j < w; ++j)
            {
                if (!VecMap[i][j].Check && VecMap[i][j].Type == 1)
                {
                    Find_Island(VecMap, i, j);
                    ans++;
                }
            }
 
        cout << ans << "\n";
    }
}