[BOJ 21232] Comfortable Cows

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

21232번: Comfortable Cows

 

- 문제 요약

 

Farmer Nhoj의 목초지는 정사각형의 형태입니다.

이 목초지는 현재 비어있으나, Nhoj는 이곳에 N(1<=N<=10^5)마리의 소를 차례대로 추가하려고 합니다.

N개의 줄에 추가되는 소의 좌표 (xi, yi)가 입력됩니다. (0<=xi,yi<=1000)

소들은 수평 또는 수직으로 정확히 세 마리의 소와 인접해 있을 때 편안함을 느낍니다.

편안한 소는 우유를 잘 만들어내지 못하므로, Nhoj는 편안한 소가 없을 때까지 목초지에 소를 추가하려 합니다.

새로 추가해야 하는 소의 최소 마릿수를 1~N번째 소가 추가될 때마다 한 줄씩 출력하세요.

 

 

- 알고리즘 정리

 

현재 위치 (x, y)에 소가 추가되었는지 확인하고, 추가되지 않았다면 (x, y)에 소를 추가합니다.
그리고 상하좌우 인접 배열에 소가 있으면 수를 카운팅 해서 소가 편안한 상태인지 아닌지를 따져줍니다.
이러한 과정을 소를 추가하면서 해당 위치에 대해 반복해 주면 됩니다.

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

#define MAX 4001
int n,dx[4]={1,0,-1,0},dy[4]={0,1,0,-1},result;
bool check[MAX][MAX];
queue<pair<int,int> >q;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n;
	for(int i=0;i<n;i++){
		pair<int,int>p;
		cin>>p.first>>p.second;
		p.first+=1000,p.second+=1000;
		q.push(p);
		auto re_evaluate=[&](int x,int y){ 
			if(!check[x][y]){
				return;
			}
			int num_adj=0;
			for(int d=0;d<4;d++){
				num_adj+=check[x+dx[d]][y+dy[d]];
			}
			if(num_adj==3){
				for(int d=0;d<4;d++){
					pair<int,int>nex{x+dx[d],y+dy[d]};
					if (!check[nex.first][nex.second]){
						q.push(nex);
					}
				}
			}
		};
		while(!q.empty()){
			pair<int,int>loc=q.front(); 
			q.pop();
			if(check[loc.first][loc.second]){
				continue;
			}
			total_cows++;
			check[loc.first][loc.second]=true;
			re_evaluate(loc.first,loc.second);
			for(int d=0;d<4;d++){
				re_evaluate(loc.first+dx[d],loc.second+dy[d]);
			}
		}
		cout<<result-i<<'\n';
	}
}

코드 제출 결과