[백준/BOJ] 백준 1012번 : 유기농 배추

https://www.acmicpc.net/problem/1012

1012번: 유기농 배추

필요한 최소의 배추 흰 지렁이의 개수는 배추 덩어리 구역의 개수이다. 그러므로 덩어리 구역의 개수를 센다.

 

코드

#include <iostream>
#include <utility>
#include <cstring>
using namespace std;

int n, m, k;
int board[50][50];
int dx_dy[4][2] = { {0,-1},{0,1},{-1,0},{1,0} };

void dfsSolve(pair<int,int> here)
{
	//탐색하는 배추를 없앤다(중복 탐색하지 않기 위해)
	board[here.first][here.second] = 0;

	//인접한 부분을 dfs한다
	//단 인접한 부분이 범위를 벗어나지 않아야 하고 1 (배추)이어야 한다
	for (int i = 0; i < 4; i++)
	{
		pair<int, int> there = make_pair(here.first + dx_dy[i][0], here.second + dx_dy[i][1]);
		if (there.first >= 0 && there.first < n && there.second >= 0 && there.second < m && board[there.first][there.second] == 1)
		{
			dfsSolve(there);
		}
	}
}

//배추 덩어리 구역의 개수를 구한다
int Solve()
{
	int ret = 0;

	for(int i=0; i<n; i++)
		for (int j = 0; j < m; j++)
		{
			//배추의 덩어리 구역을 발견한것이므로
			//해당위치에서 해당 덩어리 구역을 dfs한다
			if (board[i][j] == 1)
			{
				//덩어리 구역 개수 찾은것이므로 개수 추가
				ret++;

				dfsSolve(make_pair(i, j));
			}
		}

	return ret;
}

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

	int testcase;
	int x, y;

	cin >> testcase;

	for (int t = 0; t < testcase; t++)
	{
		//테스트케이스마다 땅(board)를 0으로 초기화 한다
		memset(board, 0, sizeof(board));

		cin >> m >> n >> k;

		for (int i = 0; i < k; i++)
		{
			//해당 위치에 배추를 표시한다
			cin >> x >> y;
			board[y][x] = 1;
		}

		cout << Solve() <<"\n";
	}

	return 0;
}