[BOJ] 4963 : 섬의 개수 (C++) with DFS

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

4963번: 섬의 개수

걸린 시간 : 11분 3초

---

가장 기본적인 dfs 혹은 bfs 문제였다.

 

"간단한 경우에는" 큐를 써야하는 bfs와 달리 재귀를 사용하는 dfs가 구현이 더 편해 dfs로 구현한다.

하지만 알고리즘이 복잡해지거나 최단 경로를 구하는 등의 많은 경우에 bfs를 더 많이 쓰는 것 같다. 이 문제는 dfs로 풀었다.

 

board를 탐색하면서 섬이 발견되면 카운트해준다. 그리고 연결된 섬을 지워주는 dfs 함수를 실행시킨다. 이렇게 섬의 개수만을 세는 경우, 방문 체크를 따로 하지 않고 섬을 직접 없애는 파괴적인 코드가 더 간편하다.

 

추가로, board에 0 혹은 1 로만 데이터가 들어와 bool 형으로 쓸 수도 있겠지만, bool이든 int이든 메모리를 1바이트 차지하는 것은 똑같으므로 int 형을 쓰는 게 좋아보인다. 만약 vector 형으로 쓴다면 실제로 1비트만을 차지하므로 vector<vector<bool> > 형으로 쓰는 것은 효용이 있어보인다.

 

#include <bits/stdc++.h>

using namespace std;

int board[51][51];
int di[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dj[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
int w, h;

void dfs (int ci, int cj) {
	board[ci][cj] = 0;
	for (int k = 0; k < 8; k++) {
		int ni = ci + di[k];
		int nj = cj + dj[k];
		if (ni < 0 || ni >= h || nj < 0 || nj >= w || board[ni][nj] == 0)
			continue;
		dfs(ni, nj);
	}	
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	while(1) {
		int ans = 0;
		cin >> w >> h;
		if (w == 0 && h == 0) break;
		for (int i = 0; i < h; i++)
			for (int j = 0; j < w; j++)
				cin >> board[i][j];
				
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if (board[i][j] == 1) {
					ans++;
					dfs(i, j);
				}
			}
		}
		
		cout << ans << "\n";
	}
	return 0;
}