[백준 c++] 1012 유기농 배추

문제 설명

https://www.acmicpc.net/problem/1012
1은 배추가 심어져있는 땅이다. 해충 방지를 위한 배추흰지렁이는 인접해있는 배추로 이동 가능하기 때문에 배추가 모여있는 곳은 지렁이 한 마리면 충분하다.

아이디어

DFS로 connected component를 찾는 문제다.

1. 테스트 케이스가 여러 개 일 수 있으니 2차원 배열 a와 visited를 while문 시작부분에서 0으로 채워넣자.

2. k개 좌표를 입력받아 해당되는 땅을 1로 바꿔준다 ^.^

3. 이중 for문으로 전체 영역을 돌면서 1이면서 방문하지 않은 땅이면 dfs 시작

4. dfs는 들어온 좌표 x,y 가 방문 처리되고 4방향을 돌면서 인접한 곳에 1이면서 방문하지 않은 땅을 찾아 다시 dfs(nx,ny)

전체 코드

#include <iostream>
#include <algorithm>
using namespace std;
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };
int t, n, m, k, a[51][51], ret, visited[51][51], y, x;

void dfs(int x, int y) {
	visited[x][y] = 1;
	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (ny < 0 || nx < 0 || ny >= n || nx >= m)continue;
		if (a[nx][ny] == 1 && !visited[nx][ny]) {
			dfs(nx, ny);
		}
	}
	return;
}

int main() {
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> t;
	while (t--) {
		fill(&a[0][0], &a[0][0] + 51 * 51, 0);
		fill(&visited[0][0], &visited[0][0] + 51 * 51, 0);
		ret = 0;
        
		cin >> m >> n >> k;
		for (int i = 0; i < k; i++) {
			cin >> x >> y;
			a[x][y] = 1;
		}
		
        for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (a[i][j] == 1 && !visited[i][j]) {
					ret++; dfs(i, j);
				}
			}
		}
		cout << ret<<"\n";

	}
}