[백준 1012] 유기농 배추 (DFS)

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

DFS를 이용한 풀이입니다. BFS를이용한 풀이는 링크를 참조해주세요. https://jow1025.tistory.com/87

풀이

BFS풀이법에서 언급했듯이 배추의 요소의 갯수만 알면되므로 dfs연산을 돌리는 횟수만 알면됩니다. 

코드

#include<iostream>
#include<cstring>
using namespace std;
int map[50][50];
int check[50][50];
int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };
int m, n, k;
//가로, 세로,배추위치갯수
void dfs(int y, int x);
int main()
{
	int t;
	cin >> t;
	int x, y;
	while (t--)
	{
		memset(map, 0, sizeof(map));
		memset(check, 0, sizeof(check));
		cin >> m >> n >> k;
		int ans = 0;
		for (int i = 0; i < k; i++)
		{
			//좌표조심
			cin >> x >> y;
			map[y][x] = 1;
		}
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				if (map[i][j] == 1 && check[i][j] == 0)
				{
					dfs(i, j);
					ans++;
				}
			}
		}
		cout << ans << endl;
	}
}
void dfs(int y, int x)
{
	check[y][x] = 1;
	for (int i = 0; i < 4; i++)
	{
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx >= 0 & ny >= 0 && nx < m && ny < n)
		{
			if (map[ny][nx] == 1 && check[ny][nx] == 0)
			{
				check[ny][nx] = 1;
				dfs(ny, nx);
			}
		}
	}
}

결과