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

01. 문제

 

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

4963번: 섬의 개수

 

02. 코드

 

#include <iostream>
//#include <string>
#include <vector>
#include <algorithm>
#include <cstring> //memset
using namespace std;

const int M = 50;
int cnt;
vector<int> residence;
//string map[M];
int map[M][M];
int visited[M][M];
int w, h;

int dx[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
int dy[] = { -1, 0, 1, -1, 1, -1, 0, 1 };

void dfs(int x, int y) {
	cnt++;
	visited[x][y] = 1;

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

		if (0 <= nx && nx < h && 0 <= ny && ny < w) {
			if (map[nx][ny] == 1 && visited[nx][ny] == 0) {
				dfs(nx, ny);
			}
		}
	}
}

int main() {
	while (1) {

		memset(visited, 0, sizeof(visited));

		residence.clear();
		
		cin >> w >> h;
		
		if (w == 0 && h == 0) {
			break;
		}

		for (int i = 0; i < h; ++i) {
			for (int j = 0; j < w; ++j) {
				cin >> map[i][j];
			}
		}

		for (int i = 0; i < h; ++i) {
			for (int j = 0; j < w; ++j) {
				if (map[i][j] == 1 && visited[i][j] == 0) {
					cnt = 0;
					dfs(i, j);
					residence.push_back(cnt);
				}
			}
		}

		cout << residence.size() << endl;
	}
}