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

 

 

문제 4963번

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

4963번: 섬의 개수

 

갈 수 있는 8가지 방향을 dy, dx로 나누어 저장해준다. while문을 이용해 입력받은 값에 대한 섬의 개수를 구해준다. map 배열에 입력받은 값들을 넣어주고, map에 섬이 있는 부분인데 방문을 안 한 부분이라면 dfs를 수행해준다. 그리고 count를 올려준다. 만약 입력받은 w와 h가 0이라면 반복문을 빠져나와준다.

 

#include <iostream>
using namespace std;

int dy[] = { 0,0,-1,1,-1,-1,1,1 };
int dx[] = { 1,-1,0,0,-1,1,-1,1 };
const int MAX = 50;
int w, h;
int map[MAX][MAX];
bool visited[MAX][MAX];


void reset() {
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			map[i][j] = 0;
			visited[i][j] = 0;
		}
	}
}

void DFS(int x, int y) {
	visited[x][y] = true;
	for (int i = 0; i < 8; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx < 0 || ny < 0 || nx >= h || ny >= w) {
			continue;
		}
		if (map[nx][ny] == 1 && visited[nx][ny] == 0) {
			DFS(nx, ny);
		}
	}
}

int main() {
	while (true) {
		reset();
		cin >> w >> h;
		int count = 0;
		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) {
					DFS(i, j);
					count++;
				}
			}
		}
		cout << count << endl;
	}
}