백준 4963번: 섬의 개수

[문제 링크]

4963번: 섬의 개수

---

전체 그래프를 탐색하면서 아직 방문하지 않은 섬을 만나면 해당 섬의 좌표를 시작으로 하는 bfs를 수행하여 하나로 연결된 섬을 찾는다.

모든 좌표를 탐색했을 때 수행한 bfs 횟수가 곧 섬의 개수가 된다.

---

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

int w, h;
bool adj[50][50];
bool visited[50][50];
int dy[8] = { 0,0,-1,-1,-1,1,1,1 };
int dx[8] = { 1,-1,0,1,-1,0,1,-1 };

struct Pos {
	int y;
	int x;
};

void bfs(int startY, int startX) {
	queue<Pos> q;
	q.push({ startY, startX });
	visited[startY][startX] = true;

	while (!q.empty()) {
		int hereY = q.front().y;
		int hereX = q.front().x;
		q.pop();

		for (int i = 0; i < 8; i++) {
			int nextY = hereY + dy[i];
			int nextX = hereX + dx[i];

			if(nextY >= 0 && nextY < h && nextX >= 0 && nextX < w)
				if (adj[nextY][nextX] && !visited[nextY][nextX]) {
					q.push({ nextY, nextX });
					visited[nextY][nextX] = true;
				}
		}
	}
}

int getIslandCount() {
	int cnt = 0;

	for(int y=0; y<h; y++)
		for (int x = 0; x < w; x++) {
			if (adj[y][x] && !visited[y][x]) {
				cnt++;
				bfs(y, x);
			}
		}

	return cnt;
}

int main(void) {
	cin.tie(0);
	ios_base::sync_with_stdio(0);

	while (true) {
		cin >> w >> h;
		if (w == 0 && h == 0)
			break;
		memset(adj, false, sizeof(adj));
		memset(visited, false, sizeof(visited));

		for (int y = 0; y < h; y++) {
			for (int x = 0; x < w; x++) {
				int n;
				cin >> n;
				adj[y][x] = n;
			}
		}
				
		cout << getIslandCount() << '\n';
	}

	return 0;
}