BaekJoon 4963번: 섬의 개수(C++)

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

4963번: 섬의 개수

풀이법

1) BFS나 DFS 알고리즘을 활용하여, 연결되어 있는 섬의 개수를 세면 되는 간단한 문제이다.

2) 여러 개의 TC가 존재하므로 visited배열을 매번 초기화 시켜 주어야 한다는과 대각선 방향 또한 인접한 배열이라고 생각해야 한다는 점을 꼭 기억한다면 어렵지 않게 풀 수 있는 문제라고 생각한다.

#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <map>
#include <queue>
#include <cstring>
#define INF 987654321
using namespace std;

int n, m;
int arr[51][51];
bool visited[51][51];
int vx[8] = { 1,0,0,-1,-1,-1,1,1 };
int vy[8] = { 0,1,-1,0,-1,1,1,-1 };
int cnt = 0;

void clearVisit(int a, int b)
{
	for (int i = 0; i < a; i++)
	{
		for (int j = 0; j < b; j++)
		{
			visited[i][j] = false;
		}
	}
}
void bfs(int a,int b)
{
	queue<pair<int, int>> q;
	visited[a][b] = true;
	q.push({ a,b });
	while (!q.empty())
	{
		int nowX = q.front().first;
		int nowY = q.front().second;
		q.pop();
		for (int i = 0; i < 8; i++)
		{
			int nextX = nowX + vx[i];
			int nextY = nowY + vy[i];

			if (nextX < 0 || nextY < 0 || nextX >= n || nextY >= m)
				continue;

			if (arr[nextX][nextY] == 1 && !visited[nextX][nextY])
			{
				visited[nextX][nextY] = true;
				q.push({ nextX,nextY });
			}
		}
	}
}

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> m >> n;
	while (n != 0 && m != 0)
	{
		clearVisit(n,m);
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				cin >> arr[i][j];
			}
		}
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				if (arr[i][j] == 1 && !visited[i][j])
				{
					bfs(i, j);
					cnt++;
				}
			}
		}

		cout << cnt << "\n";
		cnt = 0;
		cin >> m >> n;
	}

}