[백준][C++]1012번. 유기농 배추

https://www.acmicpc.net/problem/1012

 

 

케이스 수만큼 반복을 해주는데 이때 그래프 크기를 입력받고 이에 맞게 assign함수를 통해 벡터를 m,n의 크기로 초기화해주고 배추가 있는 부분만 1로 수정해준다. 그리고 그래프를 전체 순회하면서 1인부분을 만난다면 BFS방식으로 순회하면서 방문처리를 해준다. 그리고 모두 방문처리가 완료되면 true를 반환해서 result값을 1 더해주고 이 result에 1이 몇번 더해졌는지 출력해주면 된다. 

 

정답코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int n, m;
bool BFS(int x, int y);
vector<vector<int>> graph;
vector < vector<bool> >visited;
int main()
{
	int t;
	cin >> t;

	for (int i = 0; i < t; i++)
	{
		m = 0, n = 0;
		int k;

		cin >> m >> n >> k;

		graph.assign(m, vector<int>(n, 0));
		visited.assign(m, vector<bool>(n, false));

		//배추 입력
		for (int i = 0; i < k; i++)
		{
			int X, Y;
			cin >> X >> Y;

			graph[X][Y] = 1;
		}

		int result = 0;

		//그래프 순회
		for (int i = 0; i < m; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if (graph[i][j] == 1 && !visited[i][j])
				{
					if (BFS(i, j)) result++;
				}
			}
		}

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

bool BFS(int x, int y)
{
	//상하좌우
	int nx[4] = { -1,1,0,0 };
	int ny[4] = { 0,0,-1,1 };

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

	while (!q.empty())
	{
		int cur_x = q.front().first;
		int cur_y = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int next_x = cur_x + nx[i];
			int next_y = cur_y + ny[i];

			if (next_x >= 0 && next_x < m && next_y >= 0 && next_y < n)
			{
				if (graph[next_x][next_y] == 1 && !visited[next_x][next_y])
				{
					visited[next_x][next_y] = true;
					q.push({ next_x,next_y });
				}
			}
		}
	}

	return true;
}