(C++) 백준 1012번 - 유기농 배추

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

문제

> 유기농 배추를 재배하기 위해 농약을 쓰지않으려면 해충보호가 중요하다. 그래서 배추흰지렁이를 구입하기로한다.
이 지렁이는 배추 근처에 서식해 해충을 잡아먹는다. 인접한 위치에 있는 배추를 보호할 수 있는데 인접은 상하좌우를 말한다.
> 밭의 크기와 배추가 심어진 위치가 주어질때, 군데군데 심어진 배추에 최소 몇마리의 지렁이가 있어야 배추를 보호할 수 있는지 구해라.

접근

배추가 있는 곳의 좌표를 잡고 사방탐색을 하여 주변에 배추가 존재하면 그래프 탐색(BFS, DFS)를 이용해 주번에 배추를 계속 탐색한다. 없다면 다음 배추가 있는 곳으로 가며 반복한다.

문제해결

> 배추의 위치를 나타낼 cabbage 벡터를 부울형으로, 사방을 나타낼 dx, dy를 정의한다. 그리고 배추를 탐색할 BFS도 정의해준다.
> 배추위치가 좌표로 들어오므로 pair로 받아주고 입력으로 들어온 배추의 위치를 큐에넣어 첫 좌표로 잡고 탐색한다.
탐색이 끝난 배추는 false로 바꿔주며 방문처리를 해준다.
> 사방 탐색을 하며 주변에 배추가 존재하면 (bool이 true)그 배추를 큐에 넣고 다시 주변을 탐색한다.
> main함수에서 테스트케이스의 개수, 밭의 크기, 배추의 위치를 입력받는다. 입력받은 조건들로 밭을만들고 0,0부터 탐색한다. 만약 배추가 존재하면 BFS함수로 주변 배추도 탐색해준다. BFS가 끝나면 cnt를 누적한다. 이는 필요한 지렁이의 수이다.
> 탐색이 끝나고나면 누적된 지렁이의 수를 출력한다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

vector<vector<bool>> cabbage;
int N, M, K;
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { -1, 1, 0, 0 };
void BFS(int r, int c)
{
	queue<pair<int, int>> q;
	q.push({ r, c });
	while (!q.empty())
	{
		pair<int, int> ground = q.front();
		int gr = ground.first;
		int gc = ground.second;
		q.pop();

		if (!cabbage[gr][gc])
			continue;
		cabbage[gr][gc] = false;

		for (int i = 0; i < 4; i++)
		{
			int nr = gr + dx[i];
			int nc = gc + dy[i];

			if (nr < 0 || nc < 0 || nr >= N || nc >= M)
				continue;

			if (cabbage[nr][nc])
			{
				q.push({ nr, nc });
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int T;
	cin >> T;
	while (T--)
	{
		cin >> N >> M >> K;
		cabbage.assign(N, vector<bool>(M, false));

		while (K--)
		{
			int a, b;
			cin >> a >> b;
			cabbage[a][b] = true;
		}

		int cnt = 0;
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < M; j++)
			{
				if (cabbage[i][j] == true)
				{
					BFS(i, j);
					cnt++;
				}
			}
		}
		cout << cnt << '\n';
	}
}

후기

앞서 단지번호 붙이기에서 사방탐색을 하고와서 은근 쉽게 해결했다. 그래도 BFS내에서 사방탐색으로 탐색 대상 찾기, 좌표로 큐에 처리하는것 등이 아직 익숙하지않아 더 해봐야겠다.