[백준 C++] 1012 유기농 배추 - 깊이우선탐색

1012번: 유기농 배추

#include <iostream>
#include <vector>
#include <list>
using namespace std;

int Map[50][50];
list<pair<int, int>> Neighbors[50][50];

void DFS(int Row, int Col)
{
	Map[Row][Col] = 0;

	for (const pair<int, int>& Neighbor : Neighbors[Row][Col])
	{
		if (Map[Neighbor.first][Neighbor.second] == 0)
		{
			continue;
		}

		DFS(Neighbor.first, Neighbor.second);
	}
}

void TestCase()
{
	for (int i = 0; i < 50; ++i)
	{
		for (int j = 0; j < 50; ++j)
		{
			Map[i][j] = 0;
			Neighbors[i][j] = list<pair<int, int>>();
		}
	}

	int M, N, K;
	cin >> M >> N >> K;
	for (int i = 0; i < K; ++i)
	{
		int X, Y;
		cin >> X >> Y;
		Map[Y][X] = 1;
	}

	// Init Neighbors
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < M; ++j)
		{
			if (Map[i][j] == 0)
			{
				continue;
			}

			// left
			if (j > 0
				&& Map[i][j - 1] == 1)
			{
				Neighbors[i][j].emplace_back(i, j - 1);
			}

			// top
			if (i > 0
				&& Map[i - 1][j] == 1)
			{
				Neighbors[i][j].emplace_back(i - 1, j);
			}

			// right
			if (j < M - 1
				&& Map[i][j + 1] == 1)
			{
				Neighbors[i][j].emplace_back(i, j + 1);
			}

			// bottom
			if (i < N - 1
				&& Map[i + 1][j] == 1)
			{
				Neighbors[i][j].emplace_back(i + 1, j);
			}
		}
	}

	// DFS
	int Count = 0;
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < M; ++j)
		{
			if (Map[i][j] == 0)
			{
				continue;
			}

			DFS(i, j);
			++Count;
		}
	}

	cout << Count << '\n';
}

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

	int T;
	cin >> T;

	for (int i = 0; i < T; ++i)
	{
		TestCase();
	}
}

---

 

모든 땅의 인접 노드를 완전 탐색 가능하도록 DFS 알고리즘을 사용했습니다.

 

각 땅을 돌면서 배추가 있는 곳에서 카운트를 해주고,

DFS함수를 호출해서 해당 노드를 포함한 인접 노드의 값을 모두 0으로 바꿔줍니다.

이 작업을 모든 땅에서 반복하면 배추가 인접된 구역이 총 몇 개인지 최종적인 카운트 값을 얻을 수 있습니다.