[백준] 1743번 음식물 피하기

1743번: 음식물 피하기

백준 유기농 배추와 거의 같은 문제이다.

그룹들 중 가장 큰 그룹을 bfs로 찾아 출력하면 된다.

 

BFS는 현재 위치의 상하좌우가 1이면 큐에 넣고

큐가 빌 때까지 계속 반복해서 비교하도록 만들면 된다.

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int Max = 0;
void Bfs(int i, int j, int N, int M, int arr[][101]) {
	int cnt = 1;
	queue < pair <int, int> > q;
	q.push(pair<int, int>(i, j));
	arr[i][j] = 0;
	int x, y;
	while (!q.empty()) {
		x = q.front().first, y = q.front().second;
		if (x - 1 >= 0 && arr[x - 1][y]) { //상
			q.push(pair<int, int>(x - 1, y));
			arr[x - 1][y] = 0;
			cnt++;
		}
		if (x + 1 <= N && arr[x + 1][y]) { //하
			q.push(pair<int, int>(x + 1, y));
			arr[x + 1][y] = 0;
			cnt++;
		}
		if (y - 1 >= 0 && arr[x][y - 1]) { //좌
			q.push(pair<int, int>(x, y - 1));
			arr[x][y - 1] = 0;
			cnt++;
		}
		if (y + 1 <= M && arr[x][y + 1]) { //우
			q.push(pair<int, int>(x, y + 1));
			arr[x][y + 1] = 0;
			cnt++;
		}
		q.pop();
	}
	Max = max(Max, cnt);
}

int main() {
	int N, M, K, r, c;
	cin >> N >> M >> K;
	int arr[101][101] = { 0 };
	for (int k = 0; k < K; k++) {
		cin >> r >> c;
		arr[r][c] = 1;
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if(arr[i][j]) Bfs(i, j, N, M, arr);
		}
	}

	cout << Max;

	return 0;
}