[4963] 섬의 개수

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

4963번: 섬의 개수

<문제>

4방향과 8방향의 차이는 방향데이터뿐이다. 항상 시계방향이나 반시계방향을 지키도록 구현하는게 좋다.

테스트케이스가 여러개 존재하는 입력인 경우, queue나 visit의 초기화를 매번 진행해주어야 한다.

특히, 조기리턴이 존재하는 경우에는 더욱 유의해야 할것이, queue가 비어있지 않은채로 bfs가 종료되기도 한다.

 

<소스코드>

#include <stdio.h>
#include <string.h>
 
#include <queue>
using namespace std;
int w, h;
int a[53][53];
bool visit[53][53];
int dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
queue<int> q;
void f(int sy, int sx) {
    int i, ty, tx, y, x;
    q.push(sy);
    q.push(sx);
    visit[sy][sx] = true;
    while (!q.empty()) {
        ty = q.front();
        q.pop();
        tx = q.front();
        q.pop();
        for (i = 0; i < 8; i++) {
            y = ty + dy[i];
            x = tx + dx[i];
            if (y < 0 || x < 0 || y >= w || x >= h) continue;
            if (visit[y][x] == false && a[y][x] == 1) {
                q.push(y);
                q.push(x);
                visit[y][x] = true;
            }
        }
    }
    return;
}
int main(void) {
    int i, j, cnt;
    while (1) {
        scanf("%d %d", &h, &w);
        if (w == 0 && h == 0) break;
        memset(visit, false, sizeof(visit));
        while (!q.empty()) q.pop();
        cnt = 0;
        for (i = 0; i < w; i++)
            for (j = 0; j < h; j++) scanf("%d", &a[i][j]);
        for (i = 0; i < w; i++) {
            for (j = 0; j < h; j++) {
                if (visit[i][j] == false && a[i][j] == 1) {
                    f(i, j);
                    cnt++;
                }
            }
        }
        printf("%d\n", cnt);
    }
    return 0;
}