[C++] 백준 4963번 섬의 개수

 

1) 문제설명

백준 Online Judge 4963번 섬의 개수

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

4963번: 섬의 개수

 

2) 아이디어

BFS 혹은 DFS를 이용해 순회하면서 섬의 개수를 찾는 문제이다.

BFS를 사용하여 순회하고 BFS가 종료되면 카운트를 세주는 방식으로 구현하였다.

여러 번의 테스트 케이스를 사용해야 하기 때문에 전역 변수로 선언된 큐와 배열을 초기화하는 것을 잊지 말자.

 

3) 코드

#include<iostream>
#include<queue>
#include<deque>
#include<string.h>
#include<math.h>
#include<cmath>
#include<stack>
#include<algorithm>

using namespace std;
int w, h, cnt = 0;
int arr[51][51];
int visited[51][51];
queue<pair<int, int>> q;
void bfs(int x, int y) {
	q.push(make_pair(x, y));
	while (!q.empty()) {
		x = q.front().first;
		y = q.front().second;
		q.pop();
		int dx[] = { -1,1,0,0,-1,-1,1,1 }; 
		int dy[] = { 0,0,-1,1,-1,1,-1,1 }; // 가로세로대각선 움직일수있다.
		for (int i = 0; i < 8; i++) {
			int nx, ny;
			nx = dx[i] + x;
			ny = dy[i] + y;
			if (nx<1 || ny<1 || nx>h || ny>w || arr[nx][ny] == 0) {
				continue;
			}
			else {
				arr[nx][ny] = 0;
				q.push(make_pair(nx, ny));

			}
		}
	}
	cnt++;
}

int main() {
	while (1) {
		cnt = 0;
		cin >> w >> h;
		if (w == 0 && h == 0) {
			break;
		}
		for (int i = 1; i <= h; i++) {
			for (int j = 1; j <= w; j++) {
				cin >> arr[i][j];
			}
		}
		for (int i = 1; i <= h; i++) {
			for (int j = 1; j <= w; j++) {
				if (arr[i][j] == 1) {
					bfs(i, j);
				}
			}
		}
		cout << cnt << endl;
		while (!q.empty()) {
			q.pop();
		}
		memset(arr, 0, sizeof(arr));
	}

}