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

백준 1012

🌲 문제 요약

인접한 다른 배추로 이동이 가능한 배추흰지렁이를 이용하여 배추밭을 보호하려고 할 때, 필요한 최소의 배추흰지렁이의 마리 수를 출력하는 문제.

🌲 문제 풀이

연결된 컴포넌트를 찾는 문제이며, DFS를 이용하여 해결한다.
상하좌우 방향으로 arr를 탐색하여, 만일 arr[ny][nx]의 값이 존재하고 visited[ny][nx]의 값이 0이라면 visited[ny][nx] = 1의 연산을 수행한 뒤, dfs 함수를 재귀적으로 호출한다.
ret을 더해나가며 배추흰지렁이의 마리 수를 계산한다.

🌲 주의

하나의 테스트 케이스가 종료될 때마다, 배열 arr와 visited를 초기화하도록 한다.

🌲 코드

#include <bits/stdc++.h>

using namespace std;
int dy[] = {-1, 0, 1, 0};
int dx[] = {0, 1, 0, -1};
int t, m, n, k, ret;
int arr[100][100];
int visited[100][100];

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

int main() {
	cin >> t;
	while (t--) {
		memset(arr, 0, sizeof(arr));
		memset(visited, 0, sizeof(visited));
		ret = 0;
		cin >> m >> n >> k;
		for (int i = 0; i < k; i++) {
			int x, y;
			cin >> x >> y;
			arr[y][x] = 1;
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (arr[i][j] && !visited[i][j]) {
					dfs(i, j);
					ret++;
				}
			}
		}
		cout << ret << '\n';
	}
	
	return 0;
}