[BOJ] #4963 섬의 개수

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

4963번: 섬의 개수

---

#1012 유기농 배추와 똑같은 문제이다. 하나 다른점이라고 하면 입력받은 행렬에 대해 상하좌우 뿐만 아니라 대각선 방향까지 접근해서 탐색을 돌려야 한다는 것. 그 부분 말고는 딱히 어려운 점이 없었다.

오랜만에 BFS 문제를 풀어보니 잘 기억이 나지 않는 부분이 있었다. 분명 다익스트라 풀때보다 매커니즘 자체는 더 쉬운데,,, 아직 몸에 익숙하지 않아서 그런 것 같다.

#include <iostream>
#include <queue>

#define MAX 51

using namespace std;

int w,h;
queue<pair<int,int>> Q;
bool visited[MAX][MAX] = { false };
int arr[MAX][MAX] = { 0 };

int Dx[8] = { -1, 1, 0, 0, -1, 1, -1, 1 };
int Dy[8] = { 0, 0, -1, 1, -1, -1, 1, 1 };
            //상 하  좌  우     대각선 처리 

void reset(int m, int n) {
    for (int i=0; i<m; i++) {
        for (int j=0; j<n; j++) {
            visited[i][j] = false;
            arr[i][j] = 0;
        }
    }
}
//초기화 함수

void BFS(int x, int y) {
    Q.push(make_pair(x,y));
    visited[x][y] = true;

    while (!Q.empty()) {
        int X = Q.front().first;
        int Y = Q.front().second;
        Q.pop();

        for (int i=0; i<8; i++) {
            int newX = X + Dx[i];
            int newY = Y + Dy[i];

            if ((newX >= 0 && newX < w) && (newY >= 0 && newY < h)) {
                if (visited[newX][newY] == false && arr[newX][newY] == 1) {
                    Q.push(make_pair(newX, newY));
                    visited[newX][newY] = true;
                }
            }
        }
    }
}

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    while(1) {
        cin >> h >> w;

        if (w==0 && h==0) return 0;

        int cnt=0;
        reset(w,h);

        for (int i=0; i<w; i++) {
            for (int j=0; j<h; j++) {
                int a;
                cin >> a; 
                arr[i][j] = a;
                //섬과 바다 지도 입력
            }
        }

        for (int i=0; i<w; i++) {
            for (int j=0; j<h; j++) {
                if (visited[i][j] == false && arr[i][j] == 1) {
                    BFS(i,j);
                    cnt++;
                }
            }
        }

        cout << cnt << '\n';
    }

    return 0;
}