[백준] #1012 유기농 배추

 

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

1068번: 트리

1. 해결방법

N, M의 최대수가 적으므로 DFS를 통해 해결하였다.

---

2. 코드

#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;

int test_case;
int M,N,K;
int ary[51][51];
int chk[51][51];
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { -1, 1, 0, 0 };
int result = 0;

void dfs(int x, int y) {
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx < 0 || nx >= M || ny < 0 || ny >= N || chk[nx][ny] || ary[nx][ny] == 0) continue;
		else {
			chk[nx][ny] = 1;
			dfs(nx, ny);
		}
	}
}

int main()
{
	cin >> test_case;
	for (int i = 0; i < test_case; i++) {
		cin >> M;
		cin >> N;
		cin >> K;
		memset(ary, 0, sizeof(ary));
		memset(chk, 0, sizeof(chk));
		result = 0;
		for (int j = 0; j < K; j++) {
			int x, y;
			cin >> x >> y;
			ary[x][y] = 1;
		}

		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				if (ary[i][j] == 1 && chk[i][j] == 0) {
					chk[i][j] = 1;
					dfs(i, j);
					result++;
				}
			}
		}
		cout << result << endl;
	}

}