백준 4963 (섬의 개수)

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

4963번: 섬의 개수

M by N 크기의 격자판이 주어지며 이 격자판 안에는 육지와 바다가 있다. 육지는 상하 좌우 대각선 방향으로 이어질 수 있으며 이렇게 이어진 육지를 하나의 섬으로 본다. 이때 섬의 개수를 구하는 문제이다.

풀이 :

BFS를 이용한 탐색

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>

using namespace std;
struct Node{
	int y, x;
};

int n, m;
int map[51][51];
int visit[51][51];
int nullVisit[51][51];
int checkY[8] = { -1, -1, -1, 0, 0, +1, +1, +1 };
int checkX[8] = { -1, 0, +1, -1, +1, -1, 0, +1 };

void bfs(int y, int x){
	queue<Node> qu;
	visit[y][x] = 1;
	qu.push({ y, x });

	while (!qu.empty()){
		Node now = qu.front();
		for (int i = 0; i < 8; ++i){
			int dy = now.y + checkY[i];
			int dx = now.x + checkX[i];
			if (dy < 0 || dx < 0 || dy >= n || dx >= m) continue;
			if (visit[dy][dx] == 1 || map[dy][dx] == 0) continue;
			visit[dy][dx] = 1;
			qu.push({ dy, dx });
		}
		qu.pop();
	}

}


int main(){
	//freopen_s(new FILE*, "tes.text", "r", stdin);
	while (1){
		cin >> m >> n;
		int cnt = 0;
		if (n == 0 && m == 0) break;

		for (int i = 0; i < n; ++i){
			for (int j = 0; j < m; ++j){
				cin >> map[i][j];
			}
		}

		memcpy(visit, nullVisit, 4 * 51 * 51);

		for (int i = 0; i < n; ++i){
			for (int j = 0; j < m; ++j){
				if (visit[i][j] == 0 && map[i][j] == 1){
					++cnt;
					bfs(i, j);
				}
			}
		}
		cout << cnt << endl;

	}
}