[C++] 1012 : 유기농 배추

실버Ⅱ

 

#include <iostream>

using namespace std;

int map[50][50] = { 0, };


int m, n;
void dfs(int x, int y) {

	if (map[x][y] == 0 || x < 0 || x >= m || y < 0 || y >= n) return;

	map[x][y] = 0;

	dfs(x - 1, y);
	dfs(x + 1, y);
	dfs(x, y - 1);
	dfs(x, y + 1);
}

int main() {
	int t, k, x, y;
	scanf("%d", &t);

	int cnt;
	//테스트 케이스 동안
	for (int i = 0; i < t; i++) {
		cnt = 0;
		//테스트 마다 m n k 새로 받기
		scanf("%d%d%d", &m, &n, &k);

		//밭의 k개의 배추 위치들 입력받기
		for (int j = 0; j < k; j++) {
			scanf("%d%d", &x, &y);
			map[x][y] = 1;
		}

		//map에서 1이면(배추면) dfs 돌기
		for (int a = 0; a < m; a++) {
			for (int b = 0; b < n; b++) {
				if (map[a][b] == 1) {
					dfs(a, b);
					cnt++;
				}
			}
		}
		printf("%d\n", cnt);
	}
}

 

DFS 응용문제로 풀었지만 BFS나 DFS 아무거나 이용해도 되는 문제다!

(BFS 배우면 BFS로도 바로 풀어보기)

 

따로 check[50][50] 배열을 만들지 않고

dfs를 탐색하는 기준이 map의 값이 1인 것이므로

map의 값을 0을 바꿔서 자동으로 더 이상 dfs가 들어가지 않도록 함

 

(원래 dfs :

map(here) = 1 -> dfs (here)

check(here) = 1인가? 아니면 next 노드ㄱㄱ

 

이 문제에서의 응용 : 

map(here) = 1 -> dfs (here), map (here)= 0

 

이 되므로 자연스럽게 차단!)

 

x y가 거꾸로 되어있어서 좀 헷갈리긴 하는데.. 별로 상관없다 어차피

x - 1 x + 1 y - 1 y + 1 다 보니까