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

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

1012번: 유기농 배추

---

//C++

#include <bits/stdc++.h>
#define F_I ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pi 3.1415926535

using namespace std;
typedef long long ll;

int m, n, k, cnt;

int arr[54][54];
int visited[54][54];
int dir[4][2] = { {0,1},{1,0},{-1,0},{0,-1} };

queue<pair<int, int> > q;

void dfs(int i, int j)
{
	visited[i][j] = 1;
	for (int k = 0; k < 4; k++)
	{
		int next_i = i + dir[k][0];
		int next_j = j + dir[k][1];
        //mark2
		if (next_i >= 0 && next_i < n && next_j >= 0 && next_j < m && visited[next_i][next_j] == 0 && arr[next_i][next_j] == 1)
		{
			dfs(next_i, next_j);
		}
	}
	return;
}

int main()
{
	F_I;
	int tc;
	cin >> tc;
	while (tc--)
	{
		memset(arr, 0, sizeof(arr));
		memset(visited, 0, sizeof(visited));
		cnt = 0;
		cin >> m >> n >> k;
		for (int i = 0; i < k; i++)
		{
			int a, b;
			cin >> a >> b;
			arr[b][a] = 1;
		}

		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				if (visited[i][j] == 0 && arr[i][j] == 1) //mark1
				{
					dfs(i, j);
					++cnt;
				}
			}
		}
		cout << cnt << '\n';
	}
}

 

> mark1 : 반복문을 차례차례 돌면서, 배추가 심어져 있는데(arr[i][j]==1) 아직 방문 하지 않은 땅이라면(visited[i][j]==0)

그 땅을 기준으로 dfs로 탐색을 시작한다. 여기에서 탐색이 끝났다는 이야기는, (마지막 땅의 상하좌우에 있는 땅 중에서 mark2를 만족하는 땅이 없다는 의미이므로), 그 범위까지 지렁이 1마리가 필요한 것이다. 그러므로 탐색이 끝난 이후, 지렁이의 마리 수를 체크하는 cnt 변수를 1 만큼 증가시킨다.

 

> mark2 : mark1의 조건을 만족한 어떠한 땅이 있을 때, 그 땅에서 다음으로 나아갈 수 있는 땅의 후보군은 상하좌우 밖에 없다. 이때, 이 3가지의 조건을 만족해야 진정으로 나아갈 수 있다.

 

 1. 밭 범위 내에 있는가? (밭의 범위를 벗어나지 않아야 한다!)

 2. 아직 방문하지 않은 땅인가?

 3. 밭에 배추가 심어져 있는가?

---