[C++] 백준 1012 유기농 배추 DFS, BFS

#include <iostream>
#include <vector>
#include <cstring>

#define MAX_LENGTH 50

using namespace std;

bool node[MAX_LENGTH][MAX_LENGTH];
bool visited[MAX_LENGTH][MAX_LENGTH];
int width, height, counts, result;


void DFS(int x, int y);

int main()
{
	int T;

	cin >> T;

	for (int i = 0; i < T; i++)
	{
		cin >> width >> height >> counts;

		result = 0;
		memset(node, NULL, sizeof(node));
		memset(visited, NULL, sizeof(visited));

		for (int j = 0; j < counts; j++)
		{
			int temp[2];
			cin >> temp[0] >> temp[1];

			node[temp[0]][temp[1]] = true;
		}

		for (int j = 0; j < width; j++)
		{
			for (int k = 0; k < height; k++)
			{
				if (node[j][k] && visited[j][k] == false)
				{
					DFS(j, k);
					result += 1;
				}
			}
		}

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

}

void DFS(int x, int y)
{
	if (node[x][y] == true && visited[x][y] == false)
	{
		visited[x][y] = true;

		if (x + 1 < width)
		{
			DFS(x + 1, y);
		}

		if (x - 1 >= 0)
		{
			DFS(x - 1, y);
		}

		if (y + 1 < height)
		{
			DFS(x, y + 1);
		}

		if (y - 1 >= 0)
		{
			DFS(x, y - 1);
		}
	}
}

 

풀이

1. DFS를 사용하여 한 정점의 상하좌우로 이동한다.
2. 없을 시에 그 구역의 리스트는 모두 순회한 것.
3. 모두 순회하였다면 방문 횟수를 증가한다.

 

주의사항

1. 상하좌우를 갈 때에 최대범위를 넘지 않도록 한다.
2. 모든 정점의 붙어있는 리스트를 검색할 수 있도록 x * y를 모두 검색해준다.
3. 밭의 지렁이의 최대 개수를 구했다면 꼭 모든 변수들을 다시 초기화해준다.

 

 

한 줄로 되어 있는 리스트들을 보다가 두 정점을 이용한 것을 보니 다음 리스트로 이어져있는 정보가 없어서 당황했지만 상하좌우로 움직여야 된다는 조건을 보고 풀게되었다.