유기농 배추 [C++]

문제 링크: https://www.acmicpc.net/problem/1012

난이도: ⚪⚪

문제 설명

문제 접근

1. 배추가 심어진 위치를 알려주기 때문에 배추가 있는 땅과 없는 땅으로 구분해 그래프를 그린다.
2. 지렁이가 이동할 수 있는 위치를 BFS로 탐색한다.
3. BFS가 완료되었다면 한 마리의 지렁이가 커버할 수 있는 지역을 모두 확인한 것이기 때문에 BFS를 실행한 횟수가 필요한 지렁이의 갯수가 된다.
   
   

제출 코드

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

// 밭을 나타내는 field와 방문 여부를 나타내는 visited 배열.
bool field[51][51]{ false };
bool visited[51][51]{ false };

// 방향 배열.
int dx[4]{0, 0, -1, 1};
int dy[4]{-1, 1, 0, 0};

// BFS 구현
void BFS(int x, int y)
{
	// 방문 기록을 남기고 q에 push한다.
	visited[x][y] = true;
	queue<pair<int,int>> q;
	q.push({x, y});
	
	while (!q.empty())
	{
		int cur_x = q.front().first;
		int cur_y = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int nx = cur_x + dx[i];
			int ny = cur_y + dy[i];
            // 범위를 검사하고,
			if (nx > -1 && ny > -1 && nx < 51 && ny < 51)
			{
            	// 방문 기록이 없으며, 배추가 있는 땅이라면
				if (!visited[nx][ny] && field[nx][ny])
				{
                	// 방문 기록을 남기고 q에 push한다.
					visited[nx][ny] = true;
					q.push({ nx, ny });
				}
			}
		}	
	}
}

// 초기화 함수
void Reset()
{
	for(int i = 0; i < 51; i++)
		for (int j = 0; j < 51; j++)
		{
			field[i][j] = false;
			visited[i][j] = false;
		}
}

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

	for (int i = 0; i < T; i++)
	{
		cin >> M >> N >> K;
		int x, y;
		// 배추 입력
		for (int j = 0; j < K; j++)
		{
			cin >> x >> y;
			field[y][x] = true;
		}
		// 지렁이 수
		int cnt = 0;
		for (int j = 0; j < M; j++)
			for (int k = 0; k < N; k++)
				// 방문한적 없고, 배추가 있는 땅이면 BFS를 실행.
				if (visited[k][j] == false && field[k][j] == true)
				{
					BFS(k, j);
					cnt++;
				}
		// 전역변수 초기화
		Reset();
		cout << cnt << '\n';
	}

	return 0;
}

결과