[백준 4963번] 섬의 개수 (C++)

문제링크 : https://www.acmicpc.net/problem/4963

#include <bits/stdc++.h> 
using namespace std;

int w, h;
int arr[50][50];
bool check[50][50];
int dw[8] = {0, 0, -1, 1, -1, -1, 1, 1};    //1 좌, -1 우
int dh[8] = { -1, 1, 0, 0, -1, 1, -1, 1 };  //1 상, -1 하

void dfs(int y, int x)
{
	for (int i = 0; i < 8; i++)  //중심 기준 8방향 탐색
	{
		int nx = x + dw[i];      //새로운 x 좌표
		int ny = y + dh[i];      //새로운 y 좌표
		if (nx < 0 || ny < 0 || nx >= w || ny >= h) { continue; } //범위 조건
		if (!check[ny][nx] && arr[ny][nx])  //이어진 길을 찾고 다시 탐색
		{
			check[ny][nx] = true;
			dfs(ny, nx);
		}
	}
}

int main()
{
	while (true)
	{
		int cnt = 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 >> arr[i][j];
			}
		}
		for (int i = 0; i < h; i++)             //각 값에 대해 깊이우선탐색
		{
			for (int j = 0; j < w; j++)
			{
				if (!check[i][j] && arr[i][j]) 
				{
					check[i][j] = true;
					dfs(i, j);
					cnt++;
				}
			}
		}
		cout << cnt << "\n";
		memset(check, 0, sizeof(check));          //체크 배열 초기화 (arr 배열은 굳이 초기화 해줄 필요 없음)
	}
}

중심 기준 8방향 탐색하며 이어진 길을 찾는다.

이후 찾은 길은 방문처리를 통하여 재방문을 방지한다.