87. 섬나라 아일랜드(BFS 활용) (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★★☆☆

#include <stdio.h>
#include <queue>

using namespace std;

int n, cnt = 0;

struct Pos
{
	int x;
	int y;
	
	Pos(int x, int y)
	{
		this -> x = x;
		this -> y = y;
	}
};

int main()
{
	scanf("%d", &n);
	
	int a[n+2][n+2]; // 외곽 라인은 전부 0으로 만들기 위해
	int dx[8] = {0, 1, 1, 1, 0 ,-1 , -1, -1}; // x좌표의 상하좌우, 대각선
	int dy[8] = {1, 1, 0, -1, -1, -1, 0, 1}; // y좌표의 상하좌우, 대각선
	
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= n; j++)
		{
			scanf("%d", &a[i][j]);
		}
	}
	
	queue<Pos> Q;
	
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= n; j++)
		{
			if(a[i][j] == 1) // 1이라면 육지로 판단
			{
				a[i][j] = 0;
				Q.push(Pos(i, j)); // queue에 Enqueue
				while(!Q.empty())
				{
					Pos temp = Q.front();
					Q.pop();
					
					for(int k = 0; k < 8; k++)
					{
						if(a[temp.x + dx[k]][temp.y + dy[k]] == 1) // 상하좌우, 대각선 확인
						{
							Q.push(Pos(temp.x + dx[k], temp.y + dy[k])); // 육지면 Enqueue
							a[temp.x + dx[k]][temp.y + dy[k]] = 0; // 중복 방지를 위해 0
						}
					}
				}
				cnt++; // 더이상 육지가 없다면 섬이 완성되었으므로 cnt++
			}
		}
	}
	
	printf("%d", cnt);
	
	return 0;
}