[알고리즘] 섬의 개수

구현 방식

• DFS를 재귀를 이용해서, 한 덩어리 다 확인 후에 다음 덩어리 확인 재귀 안쓰고 자료구조 이용해서 DFS BFS 를 해도 되긴한다.

using namespace std;

struct Pos
{
	Pos(int y, int x)
	{
		this->y = y;
		this->x = x;
	}
	int y;
	int x;
};

void solution(int N, int M);
void dfs(int N, int M, Pos& currPos);
bool canGo(Pos& nextPos, int N, int M);

int graph[51][51];
bool visited[51][51] = {};
Pos surround[8] = { {-1, 0},{1, 0},
					{0,-1},{0,1},
					{1,-1},{1,1},
					{-1,-1},{-1,1} };


int main()
{
	int N, M;
	while (true)
	{
		cin >> M >> N;
		if (!(M || N))
			break;

		for (int y = 0; y < N; y++)
			for (int x = 0; x < M; x++)
				cin >> graph[y][x];

		solution(N, M);
		fill(&visited[0][0], &visited[N][M], false);

	}
}


void solution(int N, int M )
{
	int result = 0;
	for (int y = 0; y < N; y++)
		for (int x = 0; x < M; x++)
			if (!visited[y][x])
			{
				Pos nextPos = { y, x };
				if (canGo(nextPos, N, M) && !visited[nextPos.y][nextPos.x])
				{
					result++;
					dfs(N, M, nextPos);
				}
			}

	cout << result << "\n";
}

void dfs(int N, int M, Pos& currPos)
{
	visited[currPos.y][currPos.x] = true;
	for (Pos& surr : surround)
	{
		Pos nextPos = { currPos.y + surr.y , currPos.x + surr.x};
		if (canGo(nextPos, N, M) && !visited[nextPos.y][nextPos.x])
			dfs(N, M, nextPos);
	}

}


bool canGo(Pos& nextPos,int N, int M)
{
	if (nextPos.y < 0 || N <= nextPos.y)
		return false;
	if (nextPos.x < 0 || M <= nextPos.x)
		return false;
	if (graph[nextPos.y][nextPos.x] == 0)
		return false;
	if (graph[nextPos.y][nextPos.x] == 1)
		return true;
	return false;
}