[백준] 알고리즘 4963번 - 섬의 개수 문제

#include <bits/stdc++.h>
using namespace std;
int dx[8] = {-1,-1,0,1,1,1,0,-1};
int dy[8] = {0,1,1,1,0,-1,-1,-1};
int arr[51][51];
bool check[51][51];
int w, h;
void dfs(int x,int y) {
	check[x][y] = true;
	for (int i = 0; i < 8; i++) { 
		int nx = dx[i] + x;
		int ny = dy[i] + y;
		if (nx<0 || nx>h - 1 || ny<0 || ny>w - 1) continue;
		if (arr[nx][ny] == 1&&check[nx][ny]==false) {
			check[nx][ny] = true;
			dfs(nx,ny);
		}
		
	}
}
int main(){
   ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
   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 >> arr[i][j];
		   }
	   }
	   
	   for (int i = 0; i < h; i++) {
		   for (int j = 0; j < w; j++) {
			   if (arr[i][j]==1&&check[i][j]==false) { 
				   dfs(i, j);
				   ans += 1;
			   }
		   }
	   }
	   for (int i = 0; i < h; i++) {
		   for (int j = 0; j < w; j++) {
			   arr[i][j] = 0;
			   check[i][j] = false;
		   }
	   }
	   cout << ans << "\n";
   }
}

DFS를 이용하여 문제를 해결하였습니다.

우선 입력 받는 부분을 이해해야한다.

테스트케이스가 주어지지 않았기 때문에, 계속 반복하면서 반복 종료조건인 0 0 이 입력되면 반복문을 탈출해야 한다.

그리고 하나의 테스트 케이스가 끝나게 되면 기존 배열과 체크 배열을 초기화 시켜줘야 한다.

 

dfs를 돌리는 조건문은 - arr에 입력값이 1 이고 체크 배열의 방문이 되지 않은 상태일때 dfs를 동작시킨다.