백준 1012 - 유기농 배추

그래프 탐색 알고리즘에 대해 알고 있어야 해결할 수 있는 문제입니다. 저는 BFS를 이용해 해결했습니다.

문제를 풀면서 정말 많은 문제들을 만났는데, 그 중 메모리 초과 문제를 가장 많이 겪었습니다. BFS 알고리즘을 작성할 때 open에 push를 하고 push한 정보를 방문했음을 표기하지 않으면 중복해서 들어오게 되어 메모리 초과가 발생했습니다.

#include <iostream>
#include <algorithm>
#include <deque>

int adjarr_y[] = { -1, 1, 0, 0 };
int adjarr_x[] = { 0, 0, -1, 1 };
int M, N, K;

bool grid[50][50] = { 0, };
bool closed[50][50] = { 0, };

void search(const int y, const int x)
{
	std::deque<std::pair<int, int>> open;
	open.push_back({ y, x });

	while (!open.empty())
	{
		std::pair<int, int> p = open.front();
		closed[p.first][p.second] = true;

		for (int i = 0; i < 4; i++)
		{
			int adjy = p.first + adjarr_y[i];
			int adjx = p.second + adjarr_x[i];

			if (adjy < 0 || adjy >= N || adjx < 0 || adjx >= M || closed[adjy][adjx] || grid[adjy][adjx] != 1) continue;

			open.push_back({ adjy, adjx });
			closed[adjy][adjx] = true;
		}

		open.pop_front();
	}
}

int result()
{
	for (int i = 0; i < K; i++)
	{
		int x, y;
		std::cin >> x >> y;
		grid[y][x] = true;
	}

	int wormCnt = 0;
	for (int y = 0; y < N; y++)
	{
		for (int x = 0; x < M; x++)
		{
			if (grid[y][x] == 1 && !closed[y][x])
			{
				search(y, x);
				wormCnt++;
			}
		}
	}
	return wormCnt;
}

void solve1()
{
	std::fill_n(grid[0], sizeof(grid), 0);
	std::fill_n(closed[0], sizeof(grid), 0);

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

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

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);

	int tCase;
	std::cin >> tCase;

	for (int t = 0; t < tCase; t++)
	{
		solve1();
	}

	return 0;
}