4963

그림의 나와있는 예제의 경우

5 4
1 0 1 0 0
1 0 0 0 0
1 0 1 0 1
1 0 0 1 0

이렇게 표현되는데 섬의 개수는 3개이다. 대각선까지 고려해야 한다.

dfs 탐색을 통해 섬을 찾을 것인데 순서는 왼쪽 위의 칸부터 시계방향으로 돌면서 탐색할 것이다.

dy, dx 배열은 차례대로 배열을 탐색할 수 있도록 해준다.
예를 들어, 첫번째 반복에서는 dy = -1, dx, -1인데 이렇게 되면 왼쪽 위의 칸을 탐색하게 하는 것이다.

#include <iostream>
using namespace std;

#define MAX 51

int n, m;
int map[MAX][MAX];
int visit[MAX][MAX];
int dy[] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dx[] = {-1, 0, 1, 1, 1, 0, -1, -1};

void mem_clear(){
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++){
            map[i][j] = 0;
            visit[i][j] = 0;
        }
}

void dfs(int y, int x){
    visit[y][x] = 1;

    for (int i = 0; i < 8; i++)
    {
        int ny = y + dy[i]; // now y
        int nx = x + dx[i];
        if (nx < 0 || ny < 0 || nx >= m || ny >= n)
            continue;

        if (map[ny][nx] == 1 && visit[ny][nx] == 0)
            dfs(ny, nx);
    }
}

int main(){
    int count;
    while (1)
    {
        count = 0;
        cin >> m >> n;
        if (n==0 && m==0)   break;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                cin >> map[i][j];
        
        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++)
            {
                if (map[i][j] && !visit[i][j])
                {
                    dfs(i, j);
                    count++;
                }
            }
        }
        cout << count << '\n';
        mem_clear();
    }
}