[백준] 4963 섬의 개수

[백준4936번]섬의 개수

간단한 bfs 문제.
대각선도 체크해줘야 하는것이 베리에이션.

#include <iostream>
#include <vector>
#include <string.h>
#include <queue>
#define MAXV 50
using namespace std;

int map[MAXV][MAXV];
int visit[MAXV][MAXV];
int dx[] = { -1,1,0,0,1,1,-1,-1};
int dy[] = { 0,0,-1,1,-1,1,-1,1};
int w, h;

void solution(int x, int y) {

	queue<pair<int, int>> q;
	q.push(make_pair(x, y));
	visit[x][y] = 1;

	while (!q.empty()) {
		//큐의 가장 앞에 있는 노드 꺼내기
		int fx = q.front().first;
		int fy = q.front().second;
		q.pop();

		//현재 노드에 인접한 노드 탐색

		for (int i = 0; i < 8; i++) {
			int nx = fx + dx[i];
			int ny = fy + dy[i];

			//지도를 벗어나지 않고
			if (nx >= 0 && nx < h && ny >= 0 && ny < w) {
				//섬이면서 방문하지 않았다면
				if (map[nx][ny] == 1 && visit[nx][ny] == 0) {
					q.push(make_pair(nx, ny));
					visit[nx][ny] = 1;
				}
			}
		}
	}

}

int main() {

	int count;

	while (1) {
		scanf("%d %d", &w, &h);
		memset(map, 0, sizeof(map));
		memset(visit, 0, sizeof(visit));
		count = 0;

		if (w == 0 && h == 0)
			break;

		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				scanf("%d", &map[i][j]);
			}
		}

		//전체 지도 탐색
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				//땅인데 방문하지 않았다면 방문
				if (visit[i][j] == 0 && map[i][j] == 1) {
					count++;
					solution(i, j);
				}
			}
		}
		printf("%d\n", count);
	}

	return 0;

}