유기농 배추 #1012 c++ 풀이

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

1012번: 유기농 배추

 

유기농 배추를 풀기 위해 dfs 에 대해서 공부했다.

https://wannadev.tistory.com/96

BFS, DFS c++

 

DFS관점에서 이차원 배열문제를 마주하면 각각 배열 인덱스에 대한 값을 노드로 보면 될것 같다.

 

 

#include<iostream>
#include<vector>
#include<cstring>

using namespace std;


int board[51][51];
int visited[51][51];
int ans = 0;
int dy[4] = { 0,1,0,-1 };
int dx[4] = { 1,0,-1,0 };


void dfs(int y, int x) {
	for (int i = 0; i < 4; i++) {
		if (visited[y + dy[i]][x + dx[i]] == 0 && board[y + dy[i]][x + dx[i]] == 1) {
				visited[y + dy[i]][x + dx[i]] = 1;
				dfs(y + dy[i], x + dx[i]);
		}
	}

}

int main() {
	int M, N, K,T;
	cin >> T;
	while (T--) {
		memset(board, 0, sizeof(board) );
		memset(visited, 0, sizeof(visited));
		ans = 0;

		cin >> M >> N >> K;
		for (int i = 0; i < K; i++) {
			int X, Y;
			cin >> X >> Y;
			board[Y][X] = 1;
		}
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (board[i][j] == 1 && visited[i][j]==0) {
					visited[i][j] = 1;
					dfs(i, j);
					ans++;
				}
			}

		}
		cout << ans << '\n';
		//cout << "  " << endl;
		
	}
	

	return 0;
}

1일때만 dfs 돌린다. 그 수를 센다.