[백준] C++ 1012번 유기농 배추

문제

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

1012번: 유기농 배추

 

접근 방법

인접한 배추들을 모두 탐색하는 것이므로 DFS, BFS로 문제를 접근하였다.

밭의 최대 크기가 50 *50이므로 이 크기의 이차원 배열을 선언하여 입력을 받았다.

모든 땅에 대해서 DFS를 수행하였는데 그 땅을 이미 방문하였는지에 대한 여부는 DFS를 시작한 땅의 값을 0으로 바꿔

땅의 값이 1인 경우에만 DFS를 진행하게 하였다.

땅의 상하좌우를 체크하여 모든 인접한 부분에 대해 DFS를 진행하였다.

밭의 크기를 넘어가는 땅에 대한 것은 예외 처리를 해주었다.

 

코드

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

int t, m, n, k, x, y, ans;
int field[50][50];
int xpos[4] = {0, 0, -1, 1};
int ypos[4] = {1, -1, 0, 0};

void dfs(int x, int y) {
	field[x][y] = 0;
	for (int i = 0; i < 4; i++) {
		int xx = x + xpos[i];
		int yy = y + ypos[i];
		if (xx < 0 || yy < 0 || xx >= m || yy >= n) continue;
		if (field[xx][yy] == 1) {
			dfs(xx, yy);
		}
	}
}

int main() {
	cin >> t;
	for (int q = 0; q < t; q++) {
		cin >> m >> n >> k;
		for (int i = 0; i < k; i++) {
			cin >> x >> y;
			field[x][y] = 1;
		}

		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (field[i][j] == 1) {
					dfs(i, j);
					ans++;
				}
			}
		}

		cout << ans << '\n';
		ans = 0;
		for (int i = 0; i < m; i++) {
			fill(field[i], field[i] + n, 0);
		}
	}
}