[백준] C++ 16234번 (인구 이동)

#include <iostream>
#include <cstdlib>
#include <queue>

using namespace std;

int arr[101][101];
int visited[101][101];
int availble[101][101];

int N=0;
int L=0;
int R=0;
int continue1=0;

void BFS(int i, int j, int count);

int main(void)
{
	cin>>N>>L>>R;
	
	for(int i=0; i<N; i++)
	{
		for(int j=0; j<N; j++)
		{
			cin>>arr[i][j];
		}
	}
	
	int count=0;
	
	while(true)
	{
		count++;
		for(int i=0; i<N; i++)
		{
			for(int j=0; j<N; j++)
			{
				if(availble[i][j]==0)
				{
					BFS(i,j,i*N+j+1);
				}
				
			}
		}
		
		for(int i=0; i<N; i++) //인구 이동이 이루어진 나라만 탐색 
		{
			for(int j=0; j<N; j++)
			{
				if(visited[i][j]==0)
				{
					availble[i][j]=1;
				}
				else
				{
					availble[i][j]=0; 
					visited[i][j]=0;
				}
				
			}
		}
		
		
		if(continue1==0)//인구 이동이 발생하지 않았다면 종료 
		{
			count--;
			break;
		}
		continue1=0;
	}
	cout<<count;
	
	
	return 0;
}

void BFS(int si, int sj, int count)
{
	queue<pair<int,int> > Q;
	Q.push(make_pair(si,sj));
	
	int sum=0;
	int area=0;
	
	while(!Q.empty())//상 하 좌 우로 인구 이동이 가능한지 확인 
	{
		int i=Q.front().first;
		int j=Q.front().second;
		Q.pop();
		if(abs(arr[i][j]-arr[i][j-1])>=L&&abs(arr[i][j]-arr[i][j-1])<=R&&visited[i][j-1]==0&&j-1>-1)
		{
			visited[i][j-1]=count;
			availble[i][j-1]=count;
			sum+=arr[i][j-1];
			area++;
			Q.push(make_pair(i,j-1));
			
		}
		if(abs(arr[i][j]-arr[i][j+1])>=L&&abs(arr[i][j]-arr[i][j+1])<=R&&visited[i][j+1]==0&&j+1<N)
		{
			visited[i][j+1]=count;
			availble[i][j+1]=count;
			sum+=arr[i][j+1];
			area++;
			Q.push(make_pair(i,j+1));
		}
		if(abs(arr[i][j]-arr[i-1][j])>=L&&abs(arr[i][j]-arr[i-1][j])<=R&&visited[i-1][j]==0&&i-1>-1)
		{
			visited[i-1][j]=count;
			availble[i-1][j]=count;
			sum+=arr[i-1][j];
			area++;
			Q.push(make_pair(i-1,j));
		}
		if(abs(arr[i][j]-arr[i+1][j])>=L&&abs(arr[i][j]-arr[i+1][j])<=R&&visited[i+1][j]==0&&i+1<N)
		{
			visited[i+1][j]=count;
			availble[i+1][j]=count;
			sum+=arr[i+1][j];
			area++;
			Q.push(make_pair(i+1,j));
		}
	}

	for(int i=0; i<N; i++)
	{
		for(int j=0; j<N; j++)
		{
			if(visited[i][j]==count)//인구 이동이 발생한 지역이면 
			{
				continue1=1;
				arr[i][j]=sum/area;
			}
		}
	}
}

인구 이동이 며칠 동안 발생했는지 구하는 문제이다.

 

인구 이동 조건

• 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루 동안 연다.
• 위의 조건에 의해 열어야 하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.
• 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.
• 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.
• 연합을 해체하고, 모든 국경선을 닫는다.

문제 풀이

1. 나라를 하나 선택하고 그 나라를 기준으로 너비우선탐색

2. 인구 이동이 가능한 나라들이 있으면 연합

3. 탐색 가능한 모든 나라 확인(1, 2번 반복)

4. 인구 이동이 모두 이루어졌으면 인구 이동이 불가능할 때까지 (1~3번 반복)

 

위 작업에서 주의해야 할 점

-인구 이동이 일어난 나라에 대해서만 탐색을 해주면 된다. 인구 이동이 발생하지 않은 나라까지 다음 단계에서 탐색을 하게 되면 불필요한 오버헤드로 인해 시간초과 발생

 

인구 이동이 발생한 나라에 대해서만 탐색을 해주는 이유는??

인구 이동이 발생하지 않은 나라는 인구 이동이 발생한 나라와 인접해 있기 때문에 인구 이동이 발생한 나라에 대해서만 탐색을 해줘도 충분하다. 

(인구 이동이 발생하지 않은 나라에 대해서 탐색을 해주게 되면 변경된 사항을 인지 못할 가능성이 있다. 인구 이동이 발생해야 하는데 발생하지 않는 문제가 발생)