[BOJ] 1012. 유기농 배추

문제

www.acmicpc.net/problem/1012

1012번: 유기농 배추

---

해설

DFS를 활용한 문제풀이

---

코드

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

int map[51][51];
bool visit[51][51];
int dx[] = { 0,0,-1,1 };
int dy[] = { 1,-1,0,0 };
int T, M, N, K;
int cnt;
int column, row;

void dfs(int x, int y) {

	visit[x][y] = true;
	for (int k = 0; k < 4; k++) {

		int nx = x + dx[k];
		int ny = y + dy[k];
		if (0 <= nx && nx < N && 0 <= ny && ny < M) {
			if (map[nx][ny] && !visit[nx][ny]) {
				visit[nx][ny] = true;
				dfs(nx, ny);
			}
		}
	}
}

int main() {
	cin >> T;

	while (T--)
	{
		//지렁이 초기화
		cnt = 0;
		//좌표 초기화
		memset(map, 0, sizeof(map));
		memset(visit, 0, sizeof(visit));

		cin >> M >> N >> K;
		for (int i = 0; i < K; i++) {

			cin >> column >> row;
			if (0 <= column && column < M && 0 <= row && row < N)
			{
				map[row][column] = 1;
			}
		}
		for (int i = 0; i < N; i++) { //세로
			for (int j = 0; j < M; j++) { //가로
				if (map[i][j] && !visit[i][j]) {
					dfs(i, j);
					cnt++;
				}
			}
		}

		cout << cnt << endl;
	}
	return 0;
}