[백준 BOJ][C++]4963번 섬의 개수 풀이: DFS/BFS

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

4963번: 섬의 개수

 

 이 문제는 DFS로 해결할 수 있습니다. 

 

 먼저 각 테스트 케이스마다 너비와 높이 w, h를 입력한 뒤 크기에 맞는 지도 정보를  map에 입력합니다. 

 

 지도 정보가 모두 저장되었다면 아직 방문하지 않은 땅(1)을 찾아 dfs()를 호출합니다. 

 

 이때 dfs()는 해당 땅 위치에서 연결된 모든 땅들을 탐색합니다.

 

 dfs()가 종료되면 섬이 하나 완성되었다는 것을 나타내므로 섬의 개수 cnt를 증가시켜줍니다. 

 

 이 과정을 map 내의 방문하지 않은 땅을 탐색할 때까지 반복합니다. 

 

 이때, 각 테스트 케이스를 시작할 때마다 map의 방문 여부 visit을 false로 초기화 해주어야합니다. 

 

 

#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>

using namespace std;

int w, h;
int map[51][51];
bool visit[51][51] = { false, };

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

void dfs(int x, int y) {

	visit[y][x] = true;

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

		if (tx < 0 || tx >= w || ty < 0 || ty >= h)
			continue;
		if (visit[ty][tx] || map[ty][tx] == 0)
			continue;

		dfs(tx, ty);
	}

}

int main(void) {

	while (1) {
		cin >> w >> h;

		if (w == 0 && h == 0)
			break;

		int cnt = 0;

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

		memset(visit, false, sizeof(visit));

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

		cout << cnt << endl;

	}


	return 0;
}