🙇‍♀️섬나라 아일랜드(BFS 활용)

섬나라 아일랜드의 지도가 격자판의 정보로 주어집니다.

각 섬은 1로 표시되어 상하좌우와 대각선으로 연결되어 있으며, 0은 바다입니다.

섬나라 아일랜드에 몇 개의 섬이 있는지 구하는 프로그램을 작성하세요.

섬 나라

만약 위와 같다면

▣ 입력설명
첫 번째 줄에 자연수 N(1<=N<=20)이 주어집니다.

두 번째 줄부터 격자판 정보가 주어진다.

▣ 출력설명
첫 번째 줄에 섬의 개수를 출력한다.

▣ 입력예제 1 
7
1 1 0 0 0 1 0
0 1 1 0 1 1 0
0 1 0 0 0 0 0
0 0 0 1 0 1 1
1 1 0 1 1 0 0
1 0 0 0 1 0 0
1 0 1 0 1 0 0

▣ 출력예제 1
5

🚀풀이

이 문제는 단지 번호 붙이기 문제와 유사했다.

단지 번호 붙이기의 코드를 변형해서 풀었는데, 이 문제에서는 대각선도 이어져있는 섬이라고 하기 때문에 그 부분까지 포함시켜서 풀었다.

// 대각선까지 포함하기
int dy[] = { -1, 0, 1, 0, -1, 1, -1, 1 };
int dx[] = { 0, 1, 0, -1, 1, 1, -1, -1 };
void BFS(int y, int x)
{
	int ny, nx;
	queue<pair<int, int>> q;
	q.push({ y, x });
	discovered[y][x] = 1;

	while (q.empty() == false)
	{
		pair<int, int> here = q.front();
		q.pop();

		for (int i = 0; i < 8; ++i)
		{
			ny = here.first + dy[i];
			nx = here.second + dx[i];

			if (ny < 1 || nx < 1 || ny > n || nx > n)
				continue;
			if (board[ny][nx] == 0)
				continue;
			if (discovered[ny][nx] == 1)
				continue;

			discovered[ny][nx] = 1;
			q.push({ ny, nx });
		}
	}
}

🚀전체 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int n, cnt = 0;
int board[27][27];
int discovered[27][27];
void setting()
{
	cin >> n;

	for (int y = 1; y <= n; ++y)
	{
		for (int x = 1; x <= n; ++x)
		{
			cin >> board[y][x];
		}
	}
}

int dy[] = { -1, 0, 1, 0, -1, 1, -1, 1 };
int dx[] = { 0, 1, 0, -1, 1, 1, -1, -1 };
void BFS(int y, int x)
{
	int ny, nx;
	queue<pair<int, int>> q;
	q.push({ y, x });
	discovered[y][x] = 1;

	while (q.empty() == false)
	{
		pair<int, int> here = q.front();
		q.pop();

		for (int i = 0; i < 8; ++i)
		{
			ny = here.first + dy[i];
			nx = here.second + dx[i];

			if (ny < 1 || nx < 1 || ny > n || nx > n)
				continue;
			if (board[ny][nx] == 0)
				continue;
			if (discovered[ny][nx] == 1)
				continue;

			discovered[ny][nx] = 1;
			q.push({ ny, nx });
		}
	}
}

void solve()
{
	setting();

	for (int y = 1; y <= n; ++y)
	{
		for (int x = 1; x <= n; ++x)
		{
			if (board[y][x] == 1 && discovered[y][x] == 0)
			{
				BFS(y, x);
				cnt++;
			}
		}
	}

	cout << cnt << '\n';
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//freopen("input.txt", "rt", stdin);

	solve();

	return 0;
}

참고