유기농 배추

이문제는 BFS, DFS둘중 뭐로 풀어도 상관은 없는 문제인거같다.

왜냐하면 Connected component가 몇개인지 갯수를 새면되는 문제이기때문이다.

만약 DFS로 풀경우 모든 vertex에 대해서 DFS를 다 돌려야한다.

물론 visited와 인덱스 범위를 확인을 하면서 돌려야함.

중간에 실패한 이유 ❗

DFS_ALL돌리고나서

memset하는 부분에서 헤더파일 cstring include안해서 먼저 컴파일 에러 뜨고

그다음에는

memset함수에서 인자로 arr, 0, sizeof(int) 해버림.

그러면 배열의 한칸만 0으로 메모리를 초기화를 하는데 이게 아니라

sizeof(arr)로 해주었어야되었다!

fill ❗

나는 memset으로 1또는 0으로 밖에 초기화 못하는데

fill이라는 함수가 있다.

해당문제는 tc의 수에 따라 arr, visited를 계속 써야하기 때문에

내가알고있는 memset함수를 사용하거나 fill함수를 사용해야하는데

memset은 0, 1 으로밖에 초기화가 안되는 반면

fill은 그냥 원하는 값으로 다 초기화가 가능하다는 장점이있다.

C++에서 배열 값을 특정 값으로 설정하는 함수들이 존재합니다. 대표적으로 memset(), fill() 함수가 있습니다.

fill & memset정리 블로그

cpp 코드

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
#define endl "\n"
#define MAX 51

int tc, row, col, bachu, y, x;
int arr[MAX][MAX];
int visited[MAX][MAX];
int dy[4] = {0, 1, 0, -1};
int dx[4] = {-1, 0, 1, 0};

bool Cango(int y, int x)
{
	if (y < 0 || y >= row || x < 0 || x >= col || arr[y][x] == 0) return false;
	return true;
}

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 (!Cango(ny, nx)) continue;
		if (visited[ny][nx]) continue;
		DFS(ny, nx);
	}
}

int cnt = 0;
void DFS_ALL()
{
	for (int i = 0; i < row; ++i)
	{
		for (int j = 0; j < col; ++j)
		{
			if (arr[i][j] == 0) continue;
			if (visited[i][j]) continue;
			DFS(i, j);
			++cnt;
		}
	}

	cout << cnt << endl;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> tc;
	
	for (int i = 0; i < tc; ++i)
	{
		cin >> col >> row >> bachu;
		for (int j = 0; j < bachu; ++j)
		{
			cin >> x >> y;
			arr[y][x] = 1;
		}

		DFS_ALL();
		memset(arr, 0, sizeof(arr));
		memset(visited, 0, sizeof(visited));
		cnt = 0;
	}

	return 0;
}