백준 1743 c++

2024년 2월 22일
기본적인 BFS문제이다.
각 BFS 시작위치에서 이동하는 영역의 누적값을 비교하여 최대값을 구한다.

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

using namespace std;

int N, M, K;
vector <vector<char>> graph;
vector <vector<bool>> visited;

void input_graph()
{
	int r, c;
	int i;

	cin >> N >> M >> K;
	graph.resize(N + 1, vector<char>(M + 1, '.'));
	visited.resize(N + 1, vector<bool>(M + 1, false));
	for (i = 0; i < K; i++)
	{
		cin >> r >> c;
		graph[r][c] = '#';
	}

	/*for (i = 0; i < N + 1; i++)
	{
		for (int j = 0; j < M + 1; j++)
		{
			cout << graph[i][j] << " ";
		}
		cout << "\n";
	}*/

	return;
}

int BFS(int start_y, int start_x)
{
	int count = 1;
	int i;
	int current_x, current_y, next_x, next_y;
	queue <pair<int, int>> q;
	vector <pair<int, int>> direction = { {1, 0},{0, 1},{-1, 0},{0, -1} };
	int direction_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 < direction_size; i++)
		{
			next_x = current_x + direction[i].first;
			next_y = current_y + direction[i].second;
			if ((next_x > 0 && next_x <= M) && (next_y > 0 && next_y <= N) 
				&& graph[next_y][next_x] == '#' 
				&& visited[next_y][next_x] == false)
			{
				q.push({ next_x, next_y });
				visited[next_y][next_x] = true;
				count++;
			}
		}
	}

	return count;
}

void find_result()
{
	int result = 0, temp;
	int i, j;
	
	for (i = 1; i < N + 1; i++)
	{
		for (j = 1; j < M + 1; j++)
		{
			if (graph[i][j] == '#' && visited[i][j] == false)
			{
				temp = BFS(i, j);
				if (temp > result)
				{
					result = temp;
				}
			}
		}
	}
	cout << result << "\n";

	return;
}

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

	input_graph();
	find_result();

	return 0;
}