백준 1012 C++ - 유기농 배추

Intro

문제해결 및 소스코드

#include <iostream>
#include <string.h>

using namespace std;

/*
									<규칙>
				- 지렁이는 상하좌우로 이동하며, 해충을 잡아먹어 배추를 보호한다.
				- 필요한 최소 지렁이의 수는?

                                   <문제해결>
                - 전형적인 DFS 문제로, 주의해야할것은 전역변수로 사용될 배열들을
                - 각 테스트케이스마다 초기화해주기 위해 memset 함수를 사용했다는것이다.
                - 아래와 같이 밭의 정보가 있을 때, 필요한 최소 지렁이수는 5마리이다.
    ------- +y ------->
   | 1 1 0 0 0 0 0 0 0 0    가로축을 먼저 탐색하며 (방문하지 않은곳 + 배추가 있는곳)에서 DFS를 호출한다.
   | 0 1 0 0 0 0 0 0 0 0    DFS에서는 상하좌우로 탐색하며 배추가있을경우 그곳에서 다시 DFS를 호출한다.
  +x 0 0 0 0 1 0 0 0 0 0    
   | 0 0 0 0 1 0 0 0 0 0    이를 반복하여 지렁이가 움직일 수 있는 배추영역 탐색을 끝마친 뒤, 필요한 지렁이
   | 0 0 1 1 0 0 0 1 1 1    수를 증가시키며 밭전체를 탐색한다.
   v 0 0 0 0 1 0 0 1 1 1


*/

// 상하좌우 방향배열
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };

int arr[51][51];							// .. 배추밭(가로축 y, 세로축 x)
bool visited[51][51];						// .. 방문여부

int m, n, k;								// .. 배추밭 가로길이(m) 세로길이(n)

void DFS(int x, int y)
{
	visited[x][y] = true;			// 방문기록

	// 상하좌우로 탐색
	for (int i = 0;i < 4;i++)
	{
		int nx = x + dx[i];
		int ny = y + dy[i];

		// 범위에 있는지 확인
		if (nx >= 0 && ny >= 0 && nx < n && ny < m)
		{
			if (!visited[nx][ny] && arr[nx][ny] == 1)
			{
				DFS(nx, ny);
			}
		}
	}
}

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

	int testcase;				// .. 테스트케이스
	cin >> testcase;


	for (int i = 0;i < testcase;i++)
	{
		int count = 0;			// .. 필요한 지렁이 수

		// 배열초기화(재사용)
		memset(arr, 0, sizeof(arr));
		memset(visited, 0, sizeof(visited));

		cin >> m >> n >> k;

		// 배추위치 입력
		for (int j = 0;j < k;j++)
		{
			int x, y;
			cin >> y >> x;

			arr[x][y] = 1;
		}

		// 가로축으로 먼저 탐색
		for (int j = 0; j < n;j++)
		{
			for (int r = 0; r < m;r++)
			{
				// 배추가있고, 방문하지않은곳일 때 DFS호출
				if (!visited[j][r] && arr[j][r] == 1)
				{
					DFS(j, r);		
					count++;		// 필요한 지렁이수+1
				}
				
			}
		}

		cout << count << "\n";
	}
}