백준 16234 인구이동 C++

문제

N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다.

오늘부터 인구 이동이 시작되는 날이다.

인구 이동은 하루 동안 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.

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

각 나라의 인구수가 주어졌을 때, 인구 이동이 며칠 동안 발생하는지 구하는 프로그램을 작성하시오.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <stdbool.h>
#include <cstring>
using namespace std;

int n, l, r;

int arr[51][51];
int dif[51][51][4];
int visited[51][51];
int mark[51][51];
int total, cnt;
int st;

int dx[4] = {0, 1, 0, -1};
int dy[4] = {-1, 0, 1, 0};

bool check(int x, int y) {
	if (x < 0 || y < 0 || x >= n || y >= n) {
		return false;
	}
	return true;
}

void allocate(int x, int y) {
	arr[y][x] = total;
	visited[y][x] = 1;
	for (int i = 0;i < 4;i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (check(nx, ny) == false || visited[ny][nx]) {
			continue;
		}
		if (mark[ny][nx] == st) {
			allocate(nx, ny);
		}
	}
	return;
}

void dfs(int x, int y) {
	total += arr[y][x];
	cnt++;
	for (int i = 0;i < 4;i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (dif[y][x][i] == -1) { // 만약 갈 수 없으면 체크하지 않는다
			continue;
		}
		if (mark[ny][nx] != 0) {
			continue;
		}
		if (dif[y][x][i] >= l && dif[y][x][i] <= r) {
			mark[ny][nx] = mark[y][x];
			dfs(nx, ny);
		}
	}
	return;
}

int main(void) {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	cin >> n >> l >> r;
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < n;j++) {
			cin >> arr[i][j];
		}
	}
	int ans = 0;
	while(1) {
		memset(dif, 0, sizeof(dif));
		memset(mark, 0, sizeof(mark));
		for (int i = 0;i < n;i++) {
			for (int j = 0;j < n;j++) {
				for (int w = 0;w < 4;w++) {
					int ny = i + dy[w];
					int nx = j + dx[w];
					// 위쪽
					if (check(nx, ny) == false) {
						dif[i][j][w] = -1; // 범위밖에 가서 체크할 필요가 없다
					}
					else { // 차이를 저장한다 
						dif[i][j][w] = abs(arr[i][j] - arr[ny][nx]);
					}
				}
			}
		}
		st = 1;
		for (int i = 0;i < n;i++) {
			for (int j = 0;j < n;j++) {
				if (mark[i][j] != 0) {
					continue;
				}
				else {
					// 합쳐질 수 있는 부분을 구분한다
					mark[i][j] = st;
					dfs(j, i);
					total = total / cnt;
					allocate(j, i);
					memset(visited, 0, sizeof(visited));
					total = 0, cnt = 0;
					st++;
				}
			}
		}
		if (st > n*n) {
			break;
		}
		ans++;
	}
	cout << ans << endl;
	return 0;
}