[백준] [c++] 4963번 섬의 개수

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

4963번: 섬의 개수

문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다.  두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러쌓여 있으며, 지도 밖으로 나갈 수 없다. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정...

 

단지번호붙이기(https://www.acmicpc.net/problem/2667)

유기농배추(https://www.acmicpc.net/problem/1012)

영역구하기(https://www.acmicpc.net/problem/2583)

​

와 유사한 문제

 

#include <iostream>
#include <queue>
#include <string.h>
using namespace std;
int w, h;
int arr[51][51];
int dx[] = { 0,1,0,-1,-1,1 ,-1,1};
int dy[] = { 1,0,-1,0,-1,-1,1,1 };
bool check[51][51];
queue<pair<int, int>> q;

void bfs() {
	pair<int, int> p;
	while (!q.empty()) {
		p = q.front();
		q.pop();
		for (int i = 0; i < 8; i++) {
			int nx = p.second + dx[i];
			int ny = p.first + dy[i];
			if (0 <= nx && nx < w && 0 <= ny && ny < h && arr[ny][nx] == 1&&check[ny][nx]==false) {
				check[ny][nx] = true;
				//for (int i = 0; i < h; i++) {
				//	for (int j = 0; j < w; j++) {
				//		cout<<check[i][j];
				//	}
				//	cout << endl;
				//}
				//cout << endl;
				q.push({ ny, nx });
			}
		}
	}
}
int main() {
	while (1) {
		memset(check, false, sizeof(check));
		cin >> w >> h;
		if (w == 0 && h == 0) {
			break;
		}
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				cin >> arr[i][j];
			}
		}
		int cnt = 0;
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if (arr[i][j] == 1 && check[i][j] == false) {
					check[i][j] = true;
					q.push({ i,j });
					cnt++;
					bfs();
				}
			}
		}
		cout << cnt<<endl;
	}
}