[백준] 알고리즘 C++ 1012번 - 유기농 배추문제

문제

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

1012번: 유기농 배추

소스코드

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int arr[51][51];
int check[51][51];
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
queue<pair<int,int>> qu;
int n, m, k;
void bfs(int x, int y) {
	qu.push({ x,y });
	check[x][y] = true;
	while (!qu.empty()) {
		int ox = qu.front().first;
		int oy = qu.front().second;
		qu.pop();
		for (int i = 0; i < 4; i++) {
			int nx = ox + dx[i];
			int ny = oy + dy[i];
			if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
			if (arr[nx][ny] == 1&&!check[nx][ny]) {
				qu.push({ nx,ny });
				check[nx][ny] = true;
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int T;
	cin >> T;
	while (T--) {
		cin >> m >> n >> k;
		int ans = 0;
		for (int i = 0; i < k; i++) {
			int x, y;
			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&&!check[i][j]) {
					bfs(i, j);
					ans++;
				}
			}
		}
		cout << ans << "\n";
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				arr[i][j] = 0;
				check[i][j] = false;
			}
		}
	}
}

해설

문제는 간단합니다.

배추가 있는 곳에 흰 지렁이를 심어서 배추를 해충으로부터 보호하고 싶어합니다.

결국 모든 경우의 수를 다돌면서 배추가 있는 부분을 개수를 세달라는 문제입니다.

하지만 인접한 배추의 경우는 배추흰지렁이1마리로 충분하다고 합니다.

최소한, 인접 = BFS를 먼저 떠올려서 문제를 해결해보았습니다.

하나의 배추를 가진 좌표에서 인접한 부분을 탐색해주면 되는 문제입니다.

 

테스트케이스를 통해 입력받아 여러가지 입력을 받으므로 하나의 테스트가 끝난 후에는 배열과 체크배열을 초기화시켜주는 것을 잊지말아야 합니다.!