백준 [1012] 유기농 배추

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

1012번: 유기농 배추

 

	#include<iostream>
	#include<cstring>
	using namespace std;
	int map[51][51];
	bool visited[51][51];
	int T, M, N, K;
	int dx[4] = { 0,0,-1,1 };
	int dy[4] = { 1,-1,0,0 };
	void dfs(int x, int y) {
	if (!map[x][y] || visited[x][y])
	return;
	visited[x][y] = true;
	for (int i = 0; i < 4; i++) {
	int nx = x + dx[i];
	int ny = y + dy[i];
	if (nx >= 0 && nx < M && ny >= 0 && ny < N) {
	dfs(nx, ny);
	}
	}
	}
	int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int X, Y;
	cin >> T;
	for (int i = 0; i < T; i++) {
	int ans = 0;
	memset(visited, false, sizeof(visited));
	memset(map, 0, sizeof(map));
	cin >> M >> N >> K;
	for (int i = 0; i < K; i++) {
	cin >> X >> Y;
	map[X][Y] = 1;
	}
	for (int i = 0; i < M; i++) {
	for (int j = 0; j < N; j++) {
	if (!visited[i][j] && map[i][j]) {
	ans++;
	dfs(i, j);
	}
	}
	}
	cout << ans << '\n';
	}
	return 0;
	}

view raw 1012.cpp hosted with ❤ by GitHub

dfs / bfs

dfs 시작점이 방문한적 없고 1이면 수를 1 증가시켜준다음 dfs함수를 실행한다.

탐색 도중 해당칸이 0이거나 방문한 적이 있으면 리턴한다.

또한, 테스트케이스가 여러 개이므로 각 경우마다 배열을 초기화해주는 작업이 필요하다.

-> memset(배열, 초기화하고 싶은 값, sizeof(배열));

memset은 cstring을 헤더로 사용한다. 

(visual studio에서는 헤더를 포함시키지 않아도 에러가 나지 않았는데, 제출할 때 컴파일 에러가 남)