백준 - 4963 섬의 개수

본 문제의 요구사항은 다음과 같다

정사각형 배열이 육지와 바다로 표시되는데 육지이면 1 섬이면 0으로 표시된다.

서로 다른 육지가 이동할수 없다면 이들은 각각 다른 섬이다. 즉 임의의 A, B 사이에 가로, 세로 그리고 대각선 방향으로 인접되어 있지 않아야 섬으로 인정된다.

 

아래 그림의 경우 모든육지는 대각선 방향으로 이어져 있기 때문에 한개의 섬으로 취급된다.

주어진 배열에서 섬이 몇개인지 구하는 프로그램을 작성하여야 한다.

 

본문제를 풀수 있는 방법은 여러가지 가 있겠지만, DFS , BFS 로 풀이하는 것이 괜찮아 보인다.

 

step1) 방문하지 않은 임의의 육지를 방문한다.

step2) 인접한 8방향의 위치중 육지인 곳을 방문한다.

step3) step2 에서 방문한 각 육지에서 인접된 방문되지 않은 육지를 방문한다.

step4) 더이상 방문할 곳이 없을때까지 step3 을 반복한다.

step5) 모든 육지를 다 방문할 때 까지 step1~4 를 반복한다. 총 반복회수가 곧 섬의 개수가 된다.

 

배열에서 DFS 탐색을 하되 육지는 1 , 섬은 0 이므로 육지를 방문할 때마다 값을 0 으로 바꾸어주면 된다.

각 육지에서 인접한 8곳을 탐색하기 위해서는 배열로 테이블을 만들면된다.

 

#include <iostream>
#include <vector>

using namespace std;
void Process(int width, int height);
void DFS(int w, int h, vector<vector<int>> & data);
int main()
{
	int w, h;

	while(1)
	{
		cin >> w >> h;
		if (!w && !h) break;

		Process(w, h);
	}
	return 0;
}

void Process(int width, int height)
{
	vector<vector<int>> data;

	for (int h = 0; h < height; h++)
	{
		vector<int> line;
		for (int w = 0; w < width; w++)
		{
			int d;
			cin >> d;
			line.push_back(d);
		}
		data.push_back(line);
	}
	int count = 0;
	for (int h = 0; h < height; h++)
	{
		for (int w = 0; w < width; w++)
		{
			if (data[h][w] == 1)
			{
				data[h][w] = 0;
				DFS(w, h, data);
                count++;
			}
		}
	}
	cout << count << endl;
}

void DFS(int w, int h, vector<vector<int>> & data)
{
	int tbl[8][2] = { {-1, -1} , {-1, 0} , {-1, 1} , {0, -1} , { 0, 1} , {1, -1}, {1, 0} , {1,1} };
	for (int i = 0; i < 8; i++)
	{
		int t_w = w + tbl[i][0];
		int t_h = h + tbl[i][1];
		if (t_h < 0 || t_h >= data.size() || t_w < 0 || t_w >= data[0].size()) continue;
		if (data[t_h][t_w] == 1)
		{
			data[t_h][t_w] = 0;
			DFS(t_w, t_h, data);
		}
	}
}