BOJ 4963 섬의 개수

문제출처 : https://www.acmicpc.net/problem/4963

1. 문제요약

- 상하좌우 및 4방향 대각선으로 연결된 섬의 개수

2. 접근방법

- dfs, bfs

3. 시간복잡도

- O(n)

4. 회고

소스코드

#include<iostream>
using namespace std;

int t, w, h, map[51][51], ans;
int dx[8] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int dy[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };

void dfs(int r, int c){
	map[r][c] = 0;

	for (int k = 0; k < 8; k++){
		int nr = r + dx[k];
		int nc = c + dy[k];

		if (0 <= nr && nr < h && 0 <= nc && nc < w && map[nr][nc]){
			dfs(nr, nc);
		}
	}
}

int main(void){
	while (cin >> w >> h && w !=0 && h != 0){
		for (int i = 0; i < h; i++){
			for (int j = 0; j < w; j++){
				cin >> map[i][j];
			}
		}
		ans = 0;
		for (int i = 0; i < h; i++){
			for (int j = 0; j < w; j++){
				if (map[i][j]){
					ans++;
					dfs(i, j);
				}
			}
		}
		cout << ans << "\n";
	}
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]