백준 1012 - 유기농 배추

이 문제는 DFS로 재귀로 문제를 풀 수 있었다. 우선 x기준 4방향, y기준 4방향을 배열에 넣어주고 현재 보고 있는 기준으로 다 돌려보고 배추가 있는지 찾고 있다면 바로 들어가서 탐색하고 나온다. 처음에는 stack에 넣어서 돌렸는데 시간초과가 났다. 그래서 재귀로 바꾸었더니 해결할 수 있었다.

 

www.acmicpc.net/problem/1012

1012번: 유기농 배추

 

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

vector <pair<int, int>> way;

int m, n, k;
int arr[51][51];

int xx[4] = { 0,1,0,-1 };
int yy[4] = { 1,0,-1,0 };

void find(int x, int y) {
	if (arr[x][y] == 1) {
		arr[x][y] = 0;
		for (int s = 0; s < 4; s++) {
			int a = xx[s] + x;
			int b = yy[s] + y;
			if (a >= 0 && y >= 0 && a < m && b < n) {
				find(a, b);
			}
		}
	}
}
int main() {
	int testcase;
	cin >> testcase;
	
	while (testcase--) {
		cin >> m >> n >> k;
		for (int i = 0; i < k; i++) {
			int a, b;
			cin >> a >> b;
			way.push_back({ a, b });
			arr[a][b] = 1;
		}

		int ans = 0;

		for (int i = 0; i < way.size(); i++) {
			if (arr[way[i].first][way[i].second] == 1) {
				find(way[i].first, way[i].second);
				ans++;
			}
		}
		cout << ans << '\n';
	}

}