[백준] 1012번 유기농 배추 C++ 문제풀이

https://docs.google.com/forms/d/e/1FAIpQLSdZT0EGrU9YrYOU0lqHelC4cDRry-35RLb3QwLoCpxKCH7yKQ/viewform

Google Forms: 로그인

문제 풀이

 DFS를 이용해 문제를 해결했다.

visited 배열을 만들어서 방문 여부와 land값이, 1인 경우 count를 진행했다.

소스 코드\

#include <iostream>
using namespace std;

int M, N, K;
int dx[4] = { 0,0,-1,1 };
int dy[4] = { 1,-1,0,0 };
bool check[51][51];
int land[51][51];
int cnt;

void dfs(int x, int y) {
	if (check[x][y] == true) {
		return;
	}
	else {
		check[x][y] = true;
		if (land[x][y] == 1) {
			for (int i = 0; i < 4; i++) {
				int row = x + dx[i];
				int col = y + dy[i];
				if (0 <= row && row < M && 0 <= col && col < N) {
					if (land[row][col] == 1) {
						dfs(row, col); // 1이면 연속으로 한거.
					}
				}
			}
		}
	}
}

void init() {
	for (int i = 0; i < 51; i++) {
		for (int j = 0; j < 51; j++) {
			check[i][j] = false;
			land[i][j] = 0;
		}
	}
}

int main() {
	int T;
	cin >> T;
	for (int i = 0; i < T; i++) {
		init();
		cin >> M >> N >> K;
		for (int j = 0; j < K; j++) {
			int x, y;
			cin >> x >> y;
			land[x][y] = 1;
		}
		cnt = 0;
		for (int row = 0; row < M; row++) {
			for (int col = 0; col < N; col++) {
				if (land[row][col] == 1 && check[row][col] == false)
					cnt += 1;
				dfs(row, col);
			}
		}
		cout << cnt << '\n';
	}
}