1012) 유기농 배추 (C++)

출처 

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

1012번: 유기농 배추

 내 풀이 

#include<iostream>
#include<queue>

using namespace std;

void BFS(int start, int end);
void Reset(int start, int end);

int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };

int map[51][51];	//밭의 최대 길이 
bool visited[51][51];	//방문 확인 BFS

int T = 0;	//테스트 케이스
int M = 0, N = 0;	//가로, 세로 길이 	
int cabbage = 0;	// 배추 
int worm = 0;		//지렁이 

int main()
{
	cin >> T;	//테스트 케이스 입력

	for (int Test = 0; Test < T; Test++)
	{
		Reset(M, N);	// 밭, 방문확인 초기화 

		cin >> M >> N >> cabbage;	//가로 세로 배추 길이 입력 받음

		int x = 0, y = 0;	//입력 받을 가로 세로 값
		//배추 위치값 받음 
		for (int i = 0; i < cabbage; i++)
		{
			cin >> x >> y;
			map[x][y] = 1;
		}

		//맵 하나씩 확인하면서 만일 배추가 있고 방문하지 않았을 경우 
		for (int i = 0; i < M; i++)
		{
			for (int j = 0; j < N; j++)
			{
				if (map[i][j] == 1 && !visited[i][j])
				{
					BFS(i,j);
					worm++;
				}
			}
		}
		cout << worm << endl;
		worm = 0;	//다음 케이스에 받을 지렁이 초기화 
	}
}


void BFS(int start, int end)
{
	queue<pair<int, int>> q;
	visited[start][end] = true;
	q.push({ start,end });

	//가로 세로 값 받고 상하좌우로 배추 있나 체크 
	while (!q.empty())
	{		
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (nx < 0 || ny < 0 || nx >= M || ny >= N) continue;

			if (map[nx][ny] == 1 && !visited[nx][ny])
			{
				visited[nx][ny] = true;
				q.push({ nx,ny });
			}
		}
	}
}

void Reset(int start, int end)
{
	for (int i = 0; i < start; i++)
	{
		for (int j = 0; j < end; j++)
		{
			map[i][j] = 0;
			visited[i][j] = false;
		}
	}
}

 해설

기존에 풀던 BFS 방식으로 풀어보았다. 배추 개수만큼 좌표를 입력받고 배추 밭 크기만큼 반복문을 돌려서 

배추가 있는 지역을 체크 후 BFS로 인접한 영역은 방문처리하여 지렁이 하나당 배추를 보호할 수 있는 영역을

체크하였다. 이후 지렁이 수 출력 

 

 새로 안 것 

BFS