백준 4963 - 섬의 개수


Tags : DFS


문제

백준 4963 - 섬의 개수

image


풀이

image

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;

int w, h;
int arr[51][51];
bool chk[51][51];

int dX[8] = { -1,-1,0,1,1,1,0,-1 };
int dY[8] = { 0,1,1,1,0,-1,-1,-1 };

void DFS(int y, int x)
{
    chk[y][x] = true;

	for (int i = 0; i < 8; ++i)
	{
		int newX = x + dX[i];
		int newY = y + dY[i];

		if (newX < 0 || newX > w
			|| newY <0 || newY >h)
			continue;

		if (arr[newY][newX] == 1 && !chk[newY][newX])
			DFS(newY, newX);
	}
}

int main()
{
    vector<int> ans;

	do
	{
		int num = 0;
		memset(arr, 0, sizeof(arr));
		memset(chk, 0, sizeof(chk));

		cin >> w >> h;

		for (int i = 0; i < h; ++i)
		{
			for (int j = 0; j < w; ++j)
				cin >> arr[i][j];
		}

		for (int i = 0; i < h; ++i)
		{
			for (int j = 0; j < w; ++j)
			{
				if (arr[i][j] == 1 && !chk[i][j])
				{
					DFS(i, j);
					++num;
				}
			}
		}
		ans.push_back(num);
	} while (w > 0 && h > 0);

	ans.resize(ans.size() - 1);

	for (auto a : ans)
		cout << a << '\n';
}