백준 11123 c++

간단한 BFS 문제이다. 매 회차마다 graph와 visitied를 초기화 해야 한다.

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

using namespace std;

vector<pair<int, int>>direction{ {1, 0}, {0, 1}, {-1, 0}, {0, -1} };

void input_graph(vector <vector<char>> &graph, vector <vector<bool>> &visited)
{
	int H, W;
	int i, j;

	cin >> H >> W;
	graph.resize(H, vector<char>(W, '.'));
	visited.resize(H, vector<bool>(W, false));
	for (i = 0; i < H; i++)
	{
		for (j = 0; j < W; j++)
		{
			cin >> graph[i][j];
		}
	}

	return;
}

void BFS(vector <vector<char>>& graph, vector <vector<bool>>& visited, int start_x, int start_y, int H, int W)
{
	int i;
	int current_x, current_y, next_x, next_y;
	queue <pair<int, int>> q;
	int d_size = direction.size();

	q.push({ start_x, start_y });
	visited[start_y][start_x] = true;
	while (!q.empty())
	{
		current_x = q.front().first;
		current_y = q.front().second;
		q.pop();
		for (i = 0; i < d_size; i++)
		{
			next_x = current_x + direction[i].first;
			next_y = current_y + direction[i].second;
			if ((next_x >= 0 && next_x < W) && (next_y >= 0 && next_y < H)
				&& graph[next_y][next_x] == '#'
				&& visited[next_y][next_x] == false)
			{
				q.push({ next_x, next_y });
				visited[next_y][next_x] = true;
			}
		}
	}

	return;
}

void find_answer(vector <vector<char>>& graph, vector <vector<bool>>& visited)
{
	int i, j;
	int H = graph.size(), W = graph[0].size();
	int answer = 0;

	for (i = 0; i < H; i++)
	{
		for (j = 0; j < W; j++)
		{
			if (graph[i][j] == '#' && visited[i][j] == false)
			{
				BFS(graph, visited, j, i, H, W);
				answer++;
			}
		}
	}
	cout << answer << "\n";

	return;
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int T;
	int i;

	cin >> T;
	for (i = 0; i < T; i++)
	{
		vector <vector<char>> graph;
		vector <vector<bool>> visited;

		input_graph(graph, visited);
		find_answer(graph, visited);
	}

	return 0;
}