백준 1012번 : 유기농 배추 [C++]

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

1012번: 유기농 배추

소스 코드 :

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
using namespace std;

bool check[51][51];
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,1,-1 };
int a[51][51];

void dfs(int x, int y, int n, int m)
{
	check[x][y] = true;
	for (int i = 0; i < 4; i++) 
	{
		int nx = x + dx[i];
		int ny = y + dy[i];

		if (nx >= 0 && nx < n && ny >= 0 && ny < m)
		{
			if (a[nx][ny] == 1)
				if (!check[nx][ny])
					dfs(nx, ny, n, m);
		}

		else continue;
	}
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int T, M, N, K;
	cin >> T;

	while (T != 0)
	{
		cin >> M >> N >> K;
		int num = 0;
		for (int i = 0; i < K; i++)
		{
			int X, Y;
			cin >> X >> Y;
			a[Y][X] = 1;
		}

		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < M; j++)
			{
				if(a[i][j]==1)
					if (!check[i][j])
					{
						num++;
						dfs(i, j, N, M);
					}
			}
		}

		cout << num << '\n';
		T--;
		memset(a, 0, sizeof(a));
		memset(check, false, sizeof(check));
	}
}

마무리 : 백준 문제를 풀면서 처음으로 풀어보는 그래프 문제이다. 학교에서 DFS와 BFS를 배웠지만 막상 접해보니 코드를 어떻게 짜야할지 잘 몰랐다.

 그래서 이 문제를 DFS로 풀 것이기 때문에 교재를 가지고 소스 코드를 참고하여 코드를 짰다. (BFS로 풀어도 상관이 없다.) 그리고 이 문제는 상하좌우를 가지고 푸는 문제이기 때문에 미리 좌표를 만들어준다.

 백준 문제를 풀 때 memset을 사용하면 #include <cstring> 을 적어줘야한다. 비주얼 스튜디오에서는 오류가 나지 않지만 백준에서는 컴파일 에러가 뜬다.