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

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

 

 

 

 

1012번: 유기농 배추

문제 풀이

dfs를 이용해 문제를 풀었다. 

for문을 이용해 배추밭인 land와 방문 여부 배열인 check를 이용해 문제를 해결했다.

배추가 있는 곳 + 방문을 안했다면 count를 해주었다.

연결된 지점에 있는 배추들은 dfs를 이용해 미리 방문 여부를 true로 설정해줬기 때문에 배추가 있더라도 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] = { false };
int land[51][51] = { 0 };
int cnt;

void dfs(int x, int y) {
	if (check[x][y] == true) //방문여부 확인
		return;
	else {
		check[x][y] = true; //방문 여부를 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);
					}
				}
			}
		}
	}
}

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';
	}
}