백준 4963번 C++

백준 4963번 섬의 개수

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

4963번: 섬의 개수

정답 코드

#include<iostream>
#include<queue>
using namespace std;
int arr[51][51];
int check[51][51];
int dx[8] = { 1,1,1,0,0,-1,-1,-1 };
int dy[8] = { 0,1,-1,1,-1,0,1,-1 };
int bfs(int b,int a) {
	queue<pair<int, int>>q;
	int area = 0;
	for (int x = 0; x < b; x++) {
		for (int y = 0; y < a; y++) {
			if (check[x][y] || arr[x][y] == 0)
				continue;
			area++;
			q.push({ x,y });
			check[x][y] = 1;
			while (!q.empty()) {
				pair<int, int>cur = q.front();
				q.pop();
				for (int x = 0; x < 8; x++) {
					int mx = cur.first + dx[x];
					int my = cur.second + dy[x];
					if (mx < 0 || my < 0 || mx >= b || my >= a)
						continue;
					if (arr[mx][my] == 0 || check[mx][my])
						continue;
					q.push({ mx,my });
					check[mx][my] = 1;

				}

			}

		}
	}
	for (int x = 0; x < b; x++) {
		for (int y = 0; y < a; y++) {
			arr[x][y] = 0;
			check[x][y] = 0;
		}
	}
	return area;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	while (1) {
		int a, b;
		cin >> a >> b;
		if (a == 0 && b == 0)
			break;
		for (int x = 0; x < b; x++) {
			for (int y = 0; y < a; y++)
				cin >> arr[x][y];
		}
		int c = bfs(b,a);
		cout << c << endl;
	}
	
}

문제 풀이

bfs를 이용해서 풀었습니다. 시작점이 한 개가 아니다 보니 이중 for문을 돌려서 시작점을 여러 개 찾았고
그 시작점을 찾을 때마다 bfs를 돌렸습니다. bfs를 시작하는 부분마다 area를 ++해서 섬의 개수를 증가시켜주었습니다. 그 밑에 조건문은 배열의 범위를 벗어나거나
이미 방문했거나 섬이 아닌 부분은 continue하도록
설정했습니다.