[백준/BOJ] 백준 4963번 : 섬의 개수

www.acmicpc.net/problem/4963

4963번: 섬의 개수

섬을 발견했을 때 해당 섬에 속한 땅을 모두 체크해서  같은 섬을 중복으로 세지 않고 섬의 개수를 구했다.

 

코드

#include <iostream>
#include <algorithm>
#include <utility>
using namespace std;

int w, h;
int board[50][50];
int check[50][50];
int dxdy[8][2] = { {0,-1},{-1,-1},{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1} };

void Pre()
{
	for (int i = 0; i < 50; i++)
		for (int j = 0; j < 50; j++)
			check[i][j] = 0;
}

void Solve(pair<int, int> here)
{
	check[here.first][here.second] = 1; //탐색한곳 체크

	//here에서 갈 수 있고, 탐색하지 않은 땅을 탐색
	for (int i = 0; i < 8; i++)
	{
		pair<int, int> there = make_pair(here.first + dxdy[i][0], here.second + dxdy[i][1]);

		if (there.first >= 0 && there.first < h && there.second >= 0 && there.second < w && board[there.first][there.second] == 1 && check[there.first][there.second] == 0)
		{
			Solve(there);
		}
	}
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int input;
	int result;

	while (1)
	{
		Pre();
		result = 0;

		cin >> w >> h;

		if (w == 0 && h == 0)
			break;

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

		for (int i = 0; i < h; i++)
			for (int j = 0; j < w; j++)
			{
				//섬을 발견했을때
				if (board[i][j] == 1 && check[i][j] == 0)
				{
					result++;

					//해당섬에 속한 땅을 체크
					Solve(make_pair(i, j));
				}
			}

		cout << result << "\n";
	}
	return 0;
}