C++ 2667 단지번호붙이기 [DFS, 그래프 탐색]

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>


void DFS(std::vector<std::string>& _boards, std::vector<std::vector<bool>>& _Visited,int _y, int _x, int* _count)
{
	int dy[] = { 0,0,1,-1 };
	int dx[] = { 1,-1,0,0 };

	_Visited[_y][_x] = true;
	++*_count;

	for (int i = 0; i < 4; i++)
	{
		int NextY = _y + dy[i];
		int NextX = _x + dx[i];

		if (NextY >= _boards.size() || NextY < 0 || NextX >= _boards[0].size() || NextX < 0)
		{
			continue;
		}

		if (_boards[NextY][NextX] == '1' && false == _Visited[NextY][NextX])
		{
			DFS(_boards, _Visited, NextY, NextX, _count);
		}
	}
}

int main()
{
	std::vector<std::string> boards;
	std::vector<std::vector<bool>> Visited;

	std::vector<int> Result;

	int N;

	std::cin >> N;

	boards.resize(N);
	Visited.resize(N);

	for (int i = 0; i < N; i++)
	{
		std::cin >> boards[i];
		Visited[i].resize(boards[i].size());
	}

	
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (boards[i][j] == '1' && false == Visited[i][j])
			{
				int Count = 0;
				DFS(boards, Visited, i, j, &Count);

				Result.push_back(Count);
			}
		}
	}

	std::cout << Result.size()<< "\n";;

	std::sort(Result.begin(), Result.end());

	for (int i = 0; i < Result.size(); i++)
	{
		std::cout << Result[i] << "\n";
	}
    
    return 0;
}