(c++)백준 4964번: 섬의 개수

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

4963번: 섬의 개수

[풀이]

간단한 bfs알고리즘으로 풀었다.

한 번 bfs를 할 때 방문하지 않은 사각형에 대해 위,아래,왼쪽,오른쪽,대각선으로 연결되어 있는 사각형을 조사하여 한 개의 섬을 모두 조사할 때까지 탐색하였다.

bfs를 돌린 횟수가 섬의 개수가 된다.

 

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

struct Island {
	int x, y;//육지의 좌표
};

int w, h;
int Map[51][51];
bool visited[51][51];
//상, 하, 좌, 우, 왼쪽 위 대각선, 오른쪽 위 대각선, 왼쪽 밑 대각선, 오른쪽 밑 대각선
const int dxy[][2] = { {-1,0},{1,0},{0,-1},{0,1},{-1,-1},{-1,1},{1,-1},{1,1} };

void bfs(int startx, int starty) {
	queue<Island>q;
	visited[startx][starty] = true;
	q.push({ startx, starty });
	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		q.pop();
		for (int i = 0; i < 8; i++) {
			int nx = x + dxy[i][0];
			int ny = y + dxy[i][1];
			//지도 범위 확인
			if (nx < 0 || nx >= h || ny < 0 || ny >= w)
				continue;
			if (Map[nx][ny] == 1 && visited[nx][ny] == false) {
				visited[nx][ny] = true;
				q.push({ nx,ny });
			}
		}
	}
}

void solution() {
	while (1) {
		cin >> w >> h;
		if (w == 0 && h == 0)
			break;
		memset(visited, false, sizeof(visited));
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				cin >> Map[i][j];
			}
		}
		int cnt = 0;
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if (Map[i][j] == 1 && visited[i][j] == false) {
					bfs(i, j);
					cnt++;
				}
			}
		}
		cout << cnt << endl;
	}
}

int main() {
	solution();
	return 0;
}