BOJ 4963 (섬의 개수)

• 문제
  정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.

  

  
  한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다.
  두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.
  
  
• 입력
  입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다.
  
  둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.
  
  입력의 마지막 줄에는 0이 두 개 주어진다.
  
  
• 출력
  각 테스트 케이스에 대해서, 섬의 개수를 출력한다.

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
int area[51][51];
bool visited[51][51];
int dy[8] = { -1,-1,-1,0,0,1,1,1 };
int dx[8] = { -1,0,1,-1,1,-1,0,1 };
int landCount;
void fast_io() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
}

void bfs(int y, int x, int height, int width) {
	queue<pair<int, int>> q;
	q.push({ y,x });
	visited[y][x] = true;

	while (!q.empty())
	{
		int currentY = q.front().first;
		int currentX = q.front().second;
		q.pop();
		for (int i = 0; i < 8; i++)
		{
			int deltaY = currentY + dy[i];
			int deltaX = currentX + dx[i];

			if (deltaY<0 || deltaY>height || deltaX<0 || deltaX>width) {
				continue;
			}

			if (area[deltaY][deltaX] != 0 && !visited[deltaY][deltaX])
			{
				q.push({ deltaY,deltaX });
				visited[deltaY][deltaX] = true;
			}
		}
	}
}

int main() {
	fast_io();
	int width = 0, height = 0;
	while (true)
	{
		cin >> width >> height;
		if (width == 0 && height == 0) {
			break;
		}
		for (int i = 0; i < height; i++) {
			for (int j = 0; j < width; j++) {
				cin >> area[i][j];
			}
		}

		for (int i = 0; i < height; i++)
		{
			for (int j = 0; j < width; j++)
			{
				if (area[i][j] && !visited[i][j]) {
					bfs(i, j, height, width);
					landCount++;
				}
			}
		}
		cout << landCount << '\n';
		landCount = 0;
		memset(visited, false, sizeof(visited));
		memset(area, 0, sizeof(area));
	}
	return 0;
}

   문제를 보자마자 그래프 탐색이라는 것을 바로 알 수 있었다. 다만 이전까지 풀었던 문제들은 대부분 상하좌우 4방향을 고려하였는데 이 문제는 대각선 까지도 연결된 것으로 보아 8방향 탐색이 필요한 문제이다.

섬의 갯수를 어떻게 count 할지 처음엔 막혔는데 BFS가 끝나면 1회 늘려주어 해결하였다.

또 입력이 0 0 일때 끝나기 때문에 기존 데이터들을 반드시 초기화 해주는 것을 잊으면 안된다.

시간 복잡도 : O(N^2)

숏코딩

#include<cstdio>
using namespace std;
int w,h,a[52][52];
void f(int x,int y){
	if(!a[x][y])return;
	a[x][y]=0;
	for(int i=x-1;i<=x+1;++i){
		for(int j=y-1;j<=y+1;++j){
			f(i,j);
		}
	}
}
int main(){
	while(1){
		scanf("%d%d",&w,&h);
		if(!w&&!h)break;
		for(int i=1;i<=h;++i){
			for(int j=1;j<=w;++j){
				scanf("%d",&a[i][j]);
			}
		}
		int c=0;
		for(int i=1;i<=h;++i){
			for(int j=1;j<=w;++j){
				if(a[i][j])f(i,j),++c;
			}
		}
		printf("%d\n",c);
	}
}

 방문 여부를 체크를 위한 배열 없이 푼 문제이다(공간 절약).
DFS를 이용하여 0인 경우는 더 나아가지 못하고 자기 자신을 0으로 만들어 추후 2번의 반복문에서 자기 자신일때는 포함시키지 않고 8방향의 위치들에서 DFS 방식으로 또 호출하는 것 같다.