[백준 16234] 인구이동

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

16234번: 인구 이동

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <list>
int N, L, R;
int terr[50 + 2][50 + 2];
struct _st
{
	int x;
	int y;
};



int visited[50 + 2][50 + 2];	// 방문 표시할 배열 
int days;
int still_union;

void input(void)
{
	scanf("%d %d %d", &N, &L, &R);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &terr[i][j]);
		}
	}
}

void init(void)
{
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			visited[i][j] = 0;				// for 루프를 돌면서 N * N 행렬 모두 탐색하기 위해 
		}
	}
}


void BFS(int x, int y)
{
	static int dir_x[4] = { 0, 0, 1, -1 };
	static int dir_y[4] = { 1, -1, 0, 0 };

	std::queue<_st> Q = {};
	Q.push({ x, y });
	visited[x][y] = 1;	

	std::list<_st> Union = {};					// BFS 들어올 때 마다 연합 생긴거 저장해줌
	Union.push_back({ x, y });					// 연합의 좌표 저장해줌
	int cnt = 1;
	int total = terr[x][y];	

	_st data = {};
	int change = 0;
	while (!Q.empty()) {
		_st data = Q.front();
		Q.pop();

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];
			if (visited[nx][ny] == 1 || nx < 0 || nx > N - 1 || ny < 0 || ny > N - 1) continue;

			int tmp = abs(terr[nx][ny] - terr[data.x][data.y]);
			if (tmp < L || tmp > R) continue;

			Union.push_back({ nx, ny });	// 연합을 이루는 좌표 저장(인구수 갱신해주기 위해 )
			visited[nx][ny] = 1;		
			cnt++;							// 연합을 이루고 있는 칸의 개수
			total += terr[nx][ny];			// 연합의 인구 수 
			Q.push({ nx, ny });
		}
	}

	for (_st area : Union) {
		terr[area.x][area.y] = total / cnt;
	}

	if (cnt > 1) still_union = 1;	// 인구이동 일어났다면 still_union = 1로 갱신
}




void migrate(void)		// 맵을 돌면서 모든 좌표 탐색 (0, 0) ~ (N - 1, N - 1)
{
	init();											// bfs 탐색용 visited배열 초기화 days마다 연합을 다시 계산해주어야 하므로
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (visited[i][j]) continue;			// 이미 방문했던 좌표는 스루
			BFS(i, j);
		}
	}
}



int main()
{
	input();
	while (1) {
		still_union = 0;	// 새로운 days마다 연합 생성 여부를 갱신해줌
		migrate();
		days++;
		if (still_union == 0) break;
	}
	printf("%d", days - 1);
	return 0;
}

이 문제도 내외 오지게 하다가 그저 빛빛 갓ㄷㅇ좌가 나를 이해시켜주셨다... .

 

 

제일 나를 힘들게 했던 조건은 "하루에 연합이 동시에 생기는 경우" 이다.  좌표 하나 받아서 "어디까지가 영역이냐"는 문제는 실버에서 마감인듯 싶다.

예컨대 예제 입력 5를 보자. 

// input
4 10 50
10 100 20 90
80 100 60 70
70 20 30 40
50 20 100 10

// output
3

상기와 같이 하루에 영역이 동시에 생기면서 인구이동이 일어나는 경우가 있으므로 총 3일이 걸리는 것이다. 

 

 

이제 코드를 살펴보자.

// migrate( ) 함수

모든 점을 탐색하면서(Flood - Fill) 만약 방문했다면 무시하고, 아직 방문하지 않은점(연합으로 소속되지 않은 점)에 대하여 BFS 함수를 실행한다. BFS함수 내에서 방문배열을 초기화하지 않도록 주의하자.

 

 

// BFS( ) 함수

BFS의 인자로 받은 지점마다 해당 점으로부터 영역이 만들어지는지 아닌지를 판단해야 하기 때문에 탐색을 진행할 큐(Q), 연합의 좌표들을 저장할 리스트(Union)을 이 함수 내에서 선언해준다. (전역으로 선언한 경우 반드시 초기화 한다)

 

그리고 연합의 일원으로 확인되면 해당 좌표를 Union 리스트에 저장하여, while 루프가 끝난 후 인구이동 때 좌표 값을 하나씩 꺼내어 갱신한다.

 

만약 연합이 한개 이상 만들어졌다면(if (cnt > 1)), still_uinon 플래그를 1로 갱신한다. 이는 이후 main함수에서 while 루프를 멈추기 위한 중요한 도구이다 !

 

 

// main( ) 함수

while( ) 루프를 계속 돌려주는 이유는,  연합이 더이상 만들어지지 않을 때 까지 인구이동을 시켜주기 위함이다. 

그래서 매 일(days)마다 still_union 플래그를 0으로 초기화시켜, migrate -> BFS 를 거치면서 still_union == 1 이면 연합이 생성된 것이므로 루프를 계속 진행하고, still_union == 0이면 더이상 연합이 생성되지 않은 것이므로 루프를 중단한다. (즉 루프 횟수 만큼의 일자 동안 인구 이동이 일어나는 것임)

 

출력에서 days - 1을 해준 이유는, 아예 인구이동이 일어나지 않았을 때도 while 루프를 빠져나오기 전에 days 변수를 1 증가시키기 때문이다. 

 

 

 

힘들었다 ^^* 

나의 화요일을 주옥같이 만들어줬지만 덕분에 또 알아가닉가.... 히히... 

이런 비슷한 문제 나왔을 때 틀리면 나레기 바보 

 

 

---

++ 22.10.19  다시 풀었는데 역시 ㄷㅇ이 코드가 더 낫네... ㅋㅋㅋㅋ 

#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <cstring>
int N, L, R;
int A[50 + 2][50 + 2];
int S[50 + 2][50 + 2];
int visited[50 + 2][50 + 2];
int Tmp[50 + 2][50 + 2];


struct _vt
{
	int num;
	int cnt;
	int sum;
};

std::vector<_vt> Info;

struct _qt
{
	int x, y;
};

std::queue<_qt> Q;


void input()
{
	scanf("%d %d %d", &N, &L, &R);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &A[i][j]);
		}
	}
}


bool chk(int x, int y, int num)
{
	static int dir_x[4] = { 0, 0 , 1, -1 };
	static int dir_y[4] = { 1, -1, 0, 0 };
	
	Q = {};

	Q.push({ x, y });
	visited[x][y] = 1;
	S[x][y] = num;
	int cnt = 1;
	int sum = A[x][y];

	while (!Q.empty()) {
		_qt data = Q.front();
		Q.pop();

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 0 || nx > N - 1 || ny < 0 || ny > N - 1) continue;
			if (visited[nx][ny]) continue;
			if ((abs(A[data.x][data.y] - A[nx][ny]) < L || abs(A[data.x][data.y] - A[nx][ny]) > R)) continue;
			Q.push({ nx, ny });
			visited[nx][ny] = 1;
			S[nx][ny] = num;
			cnt++;
			sum += A[nx][ny];
		}
	}
	if (cnt == 1) {
		S[x][y] = 0;	// 다시 원복
		return false;	// 해당 격자 하나만 존재 
	}
	
	Info.push_back({ num, cnt, sum });
	return true;
}



bool open_bound()
{
	std::fill(&visited[0][0], &visited[0][0] + sizeof(visited) / sizeof(int), 0);
	std::fill(&S[0][0], &S[0][0] + sizeof(S) / sizeof(int), 0);
	Info.clear();
	
	//flood - fill
	int num = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (visited[i][j]) continue;
			if (chk(i, j, num + 1)) num++;
		}
	}
	if (Info.empty()) return false;	// 연합 정보를 저장하는 벡터가 비었으면 연합이 만들어지지 않은 것임 
	return true;
}


void move_popu()
{
	for (int n = 0; n < Info.size(); n++) {
		int population = Info[n].sum / Info[n].cnt;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (S[i][j] == Info[n].num) Tmp[i][j] = population;
			}
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (Tmp[i][j] == 0) Tmp[i][j] = A[i][j];
		}
	}

	std::fill(&A[0][0], &A[0][0] + sizeof(A) / sizeof(int), 0);
	memcpy(A, Tmp, sizeof(Tmp));
	std::fill(&Tmp[0][0], &Tmp[0][0] + sizeof(Tmp) / sizeof(int), 0);
}





int simul()
{
	for (int d = 0; d < 2000; d++) {
		if (!open_bound()) return d;
		move_popu();
	}
}


int main()
{
	input();
	int ans = simul();
	printf("%d\n", ans);
	return 0;
}