백준 1012 - 유기농배추


Tags : DFS


문제

백준 1012 - 유기농배추

image


풀이

image

#include <iostream>
#include <string.h>
using namespace std;

int M, N, K;
int arr[50][50];
int chk[50][50];

int dX[4] = { -1,1,0,0 };
int dY[4] = { 0,0,-1,1 };

void DFS(int y, int x)
{
	chk[y][x] = true;

	for (int i = 0; i < 4; ++i)
	{
		int newX = x + dX[i];
		int newY = y + dY[i];

		if (newX < 0 || newX >= M
			|| newY < 0 || newY >= N)
			continue;

		if (arr[newY][newX] ==1 && !chk[newY][newX])
		{
			DFS(newY, newX);
		}
	}
}

int main()
{
    int T = 0;
	int x, y = 0;
	int ans = 0;

	cin >> T;

	for(int k = 0; k < T; ++k)
	{
        memset(arr, 0, sizeof(arr));
		memset(chk, 0, sizeof(chk));
		cin >> M >> N >> K;

		for (int i = 0; i < K; ++i)
		{
			cin >> x >> y;
			arr[y][x] = 1;
		}

		for (int i = 0; i < N; ++i)
		{
			for (int j = 0; j < M; ++j)
			{
				if (arr[i][j] == 1 && !chk[i][j])
				{
					DFS(i, j);
					++ans;
				}
			}
		}
		cout << ans << '\n';
		ans = 0;
	}
    
    return 0;
}