(bfs/dfs)4963 섬의 개수

bfs/dfs 연장선상의 문제였지만 푸는 데 시간이 오래걸렸다. 고난이 많았던 문제...

https://www.acmicpc.net/problem/4963

4963번: 섬의 개수

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<queue>
#define X first
#define Y second
using namespace std;

int dx[8] = { -1,-1,-1,0,1,1,1,0 };
int dy[8] = { -1,0,1,1,1,0,-1,-1 };
int w, h;
int** arr ;
bool** visited;
int cnt = 0;


void BFS(pair<int,int>start) {
    queue<pair<int,int>> q;
    q.push(start);
    visited[start.X][start.Y] = false;
 
    while (!q.empty()) {
        pair<int, int>cur = q.front();
        q.pop();

     
        for (int i = 0; i < 8; i++) {
            int nx = cur.X + dx[i];
            int ny = cur.Y + dy[i];
           
            
            if (nx < 0 || nx >= h || ny < 0 || ny >= w) { 
             
                continue; }
          
            if (visited[nx][ny] || arr[nx][ny] != 1) {
               
                continue; }
           
            visited[nx][ny] = true;
            q.push({ nx,ny });
        }
    }




}
int main() {
    cin.tie(NULL);
    cin.sync_with_stdio(false);
    cout.tie(NULL);
    while (true) {

        int connectedN = 0;

        cin >> w >> h;
        if (w == 0 && h == 0)
            break;
        arr = new int* [h];
        for (int i = 0; i < h; i++) {
            arr[i] = new int[w];
        }

        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                cin >> arr[i][j];
            }

        }




        visited = new bool* [h];
        for (int i = 0; i < h; i++) {
            visited[i] = new bool[w];
        }

        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                visited[i][j] = false;
            }


        }



        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (!visited[i][j]) {
                   
                    if (arr[i][j]) {
                        BFS({ i,j });
                        connectedN++;
                       

                    }
                }
            }
        }

        cout << connectedN<<"\n";

    }
    return 0;

}