백준 4963 섬의 개수(c++)

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

4963번: 섬의 개수

<코드>

#include <iostream>
#include <cstring>
#include <queue>
#define max 51
using namespace std;
int w,h,n,m;
int board[max][max];
bool visited[max][max] = {0};

int dir[8][2] = {{-1,0},{1,0},{0,-1},{0,1},{1,1},{-1,-1},{1,-1},{-1,1}}; //상하좌우 대각선 이동 
void dfs(int x,int y)
{
	for(int i=0;i<8;i++)
	{
		int sr = x + dir[i][0];
		int sc = y + dir[i][1];
		if(sr<0 || sc<0 || sr>h-1 || sc>w-1) continue;
		if(visited[sr][sc]) continue;
		if(!visited[sr][sc] && board[sr][sc]){
			visited[sr][sc] = true;
			dfs(sr,sc);
		}
		
	}
}
int main()
{
	while(cin>>w>>h)
	{
		int cnt = 0;
		if(w==0 && h==0) break;
		for(int i=0;i<h;i++){
			for(int j=0;j<w;j++){
				cin>>board[i][j];
			}
		}
		for(int i=0;i<h;i++)
		{
			for(int j=0;j<w;j++)
			{
				if(!visited[i][j] && board[i][j])
				{
					visited[i][j] = true;
					dfs(i,j);
					cnt++;
				}
			}
		}
		cout<<cnt<<'\n';
		memset(visited,0,sizeof(visited));
		memset(board,0,sizeof(board));
	}
}

<풀이과정>

이 문제는 flood fill의 응용 문제이다. 기존 flood fill의 알고리즘은 상하좌우로 이동할 수 있는지를 검사했지만, 이번 경우에는 대각선의 이동도 추가해줘야되기 때문에 연산을 4개 추가해줬다. [4][2]=>[8][2]로 추가해줬다.