[BOJ] 4963 :: 섬의 개수

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

0은 바다 1은 섬일때 총 섬의 개수를 구하는 문제입니다.

1로 연결된 모든 지점을 구해 그것을 한개의 섬으로 간주하고 총 섬의 개수를 구하면 됩니다.

대각선도 연결된 것으로 간주합니다.

즉 한 지점에 대해 자기자신을 주위로 8개 모두 탐색을 해야하는 것 입니다.

1인 지점이 존재하면 그 지점부터 탐색을 시작하고, 섬의 개수를 증가시켜줍니다.

자신 주위의 8개를 모두 탐색하며 1이 있다면 연결된 섬이라는 의미 이므로 0으로 변경시켜주고, 그와 연결된 섬도 탐색하기 위해 queue에 넣어 그 지점도 후에 다시 탐색될 수 있도록 합니다.

bfs방식을 이용해서 풀이 했습니다.

#include <iostream>
#include <queue>
using namespace std;
int info[52][52];
bool visited[52][52];
void search(int x, int y)
{
	queue<pair<int, int> > q;
	q.push(make_pair(x, y));
	visited[x][y] = true;
	while (!q.empty())
	{
		int a = q.front().first;
		int b = q.front().second;
		info[a][b] = 0;
		q.pop();
		if (info[a - 1][b - 1] == 1)
			q.push(make_pair(a - 1, b - 1)), info[a-1][b-1] = 0;
		if (info[a-1][b] == 1)
			q.push(make_pair(a-1, b)), info[a-1][b] = 0;
		if (info[a - 1][b + 1] == 1)
			q.push(make_pair(a - 1, b + 1)), info[a - 1][b + 1] = 0;
		if (info[a][b - 1] == 1)
			q.push(make_pair(a, b - 1)), info[a][b - 1] = 0;
		if (info[a][b + 1] == 1)
			q.push(make_pair(a, b + 1)), info[a][b + 1] = 0;
		if (info[a + 1][b - 1] == 1)
			q.push(make_pair(a + 1, b - 1)), info[a + 1][b - 1] = 0;
		if (info[a + 1][b] == 1)
			q.push(make_pair(a + 1, b)), info[a + 1][b] = 0;
		if (info[a + 1][b + 1] == 1)
			q.push(make_pair(a + 1, b + 1)), info[a + 1][b + 1] = 0;
	}
}//연결된 섬 탐색





int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(NULL);
	int w, h;
	while (1)
	{
		int cnt = 0;
		cin >> w >> h;
		if (w == 0 && h == 0)
			break;
		
		for (int i = 1; i <= h; i++)
			for (int j = 1; j <= w; j++)
			{
				cin >> info[i][j];
			}
		//정보 입력받기
		for (int i = 1; i <= h; i++)
		{
			for (int j = 1; j <= w; j++)
			{
				if (info[i][j] == 1)
				{
					cnt++;
					search(i, j);
				}
			}
		}//1인 지점 부터 섬시작, 개수증가
		cout << cnt << "\n";
	}
}