[C++] 섬나라 아일랜드(BFS)

📄문제

섬나라 아일랜드의 지도가 격자판의 정보로 주어집니다. 각 섬은 1로 표시되어 상하좌우와 대각선으로 연결되어 있으며, 0은 바다입니다. 섬나라 아일랜드에 몇 개의 섬이 있는지 구하는프로그램을 작성하세요.

 

⬇️ 입력

첫 번째 줄에 자연수 N(1<=N<=20)이 주어집니다.
두 번째 줄부터 격자판 정보가 주어진다.

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

 

⬆️ 출력

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

5

 

📝 풀이

#include <iostream>
#include <queue>
using namespace std;

bool island[21][21];

// 각 방향을 더욱 효율적으로 계산하기 위해 선언
int dx[8]{ -1, 0, 1, -1, 1, -1, 0, 1 };
int dy[8]{ -1, -1, -1, 0, 0, 1, 1, 1 };

int main()
{
	int N;
	scanf_s("%d", &N);

	queue<pair<int, int>> q;

	for (int i = 0; i < N; ++i)
		for (int j = 0; j < N; ++j)
			scanf_s("%d", &island[i][j]);

	int cnt = 0;
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			// 각 섬을 검사하여 섬이라면 인접한 섬들을 계산
			if (island[i][j] == 1)
			{
				// 섬을 시작하면서 개수를 1 더하기
				++cnt;

				q.push({ i,j });
				island[i][j] = 0;

				while (!q.empty())
				{
					int x = q.front().first;
					int y = q.front().second;
					q.pop();

					for (int k = 0; k < 8; ++k)
					{
						int xx = x + dx[k];
						int yy = y + dy[k];

						// 계산된 거리가 범위를 벗어난다면 고려하지 않아야 함
						if (xx < 0 || yy < 0 || xx > N || yy > N)
							continue;

						// 방문 가능한 모든 섬 위치를 삽입
						if (island[xx][yy] == 1)
						{
							island[xx][yy] = 0;
							q.push({ xx, yy });
						}
					}
				}
			}
		}
	}

	printf("%d", cnt);
}

• BFS를 활용하여 계산합니다.
• 2중 for문을 통해 해당 구역이 섬이라면, 해당 구역을 시작으로 인접한 영역을 모두 검사합니다.
• 더 이상 인접한 영역이 없어 queue가 비었다면, 섬 영역은 끝이며, 2중 for문을 이어서 돕니다.