C++ 1012 우기농 배추 [DFS, 그래프 탐색]

 

 

 

코드

#include <iostream>
#include <vector>

struct FValue
{
public:
	int value = 0;
	int visited = false;
};

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

	_boards[_y][_x].visited = 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].value == 1 && false == _boards[NextY][NextX].visited)
		{
			DFS(_boards,NextY, NextX, _count);
		}
	}
}

void Initboards(int _y, int _x, int _k)
{
	std::vector<std::vector<FValue>> boards;
	int result = 0;

	boards.resize(_y);

	for (int i = 0; i < _y; i++)
	{
		boards[i].resize(_x);
	}

	for (int i = 0; i < _k; i++)
	{
		int x, y;
		std::cin >> x >> y;

		boards[y][x].value = 1;
	}

	for (int i = 0; i < _y; i++)
	{
		for (int j = 0; j < _x; j++)
		{
			if (boards[i][j].value == 1 && false == boards[i][j].visited)
			{
				int Count = 0;
				DFS(boards,i, j, &Count);

				if (Count > 0)
				{
					++result;
				}
			}
		}
	}

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

int main()
{
	int T;
	std::cin >> T;

	for (int i = 0; i < T; i++)
	{
		int M, N, K;

		std::cin >> M >> N >> K;

		Initboards(N, M, K);

	}
	return 0;
}