[백준] 4863번 섬의 개수 (C++)

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

 

문제 설명

각 테스트 케이스마다 w와 h가 주어진다. 

w * h 크기의 배열이 주어지는데, 1은 땅을, 0은 바다를 의미한다.

땅은 가로, 세로, 대각선으로 움직일 수 있다. 각 테스트 케이스별로 연결된 땅의 개수를 구하는 문제이다.

마지막 테스트 케이스이라면 w와 h값으로 0이 주어진다 

 

주요 로직

1. 그래프 탐색 문제이다

각 테스트 케이스마다 visited배열을 0으로 초기화하고 깊이 우선 탐색으로 배열을 탐색한다

 

정답 코드

#include <bits/stdc++.h>

using namespace std;

int w,h, arr[55][55], visited[55][55];
int dy[8] = {-1,-1,0,1,1,1,0,-1}, dx[8] = {0,1,1,1,0,-1,-1,-1};

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

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	while(cin >> w >> h){
		fill(&arr[0][0], &arr[0][0]+55*55, 0);
		fill(&visited[0][0], &visited[0][0]+55*55, 0);
		if(w == 0 && h == 0) return 0;
		for(int i=0; i<h; i++){
			for(int j=0; j<w; j++){
				cin >> arr[i][j];
			}
		}
		int cnt = 0;
		for(int i=0; i<h; i++){
			for(int j=0; j<w; j++){
				if(visited[i][j]) continue;
				if(arr[i][j] == 0) continue;
				cnt++;
				dfs(i,j); 
			}
		}
		cout << cnt << "\n";
	}
	
	return 0;
}