백준 1012 유기농 배추

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

 

서론

dfs(재귀)로 풀이

 

---

풀이

1. 모든 칸을 일일이 확인해서 배추가 심어져있는 칸만 dfs를 실행한다.

 

2. dfs가 실행되면 출력값을+1해주고 dfs로 만들어진 영역은 전부 0으로 만들어줘서 이 영역은 다시 dfs가 실행되지 않게 한다. (dfs가 재귀를 불러올 때 재방문하지 않게 하는 목적도 있다.)

 

3. 출력값을 출력한다.

 

4. 아래 코드는 지렁이를 발견할때마다 cnt를 +1 해줘서 cnt가 k값이랑 같아지면 남은 칸을 확인하지 않는 코드를 넣었는데, 없어도 무방하다.

 

---

구현

//c++

#pragma warning(disable:4996)

#include <iostream>
#include <cstdio>

int map[51][51];
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, -1, 1 };
int cnt;

void dfs(int y, int x) {
	if (map[y][x] == 0) return;
	map[y][x] = 0;
	cnt++;

	for (int i = 0; i < 4; i++) {
		int yy = y + dy[i];
		int xx = x + dx[i];
		if (yy >= 0 && xx >= 0) dfs(yy, xx);
	}

}

int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		int m, n, k;
		scanf("%d %d %d", &m, &n, &k);
		for (int i = 0; i < k; i++) {
			int x, y;
			scanf("%d %d", &x, &y);
			map[y][x] = 1;
		}
		int result = cnt = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (cnt == k) break;
				else if (map[i][j] == 1) {
					dfs(i, j);
					result++;
				}
			}
		}
		printf("%d\n", result);
	}
}