[BOJ]백준 16234번: 인구 이동

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

16234번: 인구 이동

^- 문제링크

 

 

 

인구 이동 문제는 맞닿아있는 국가와의 인구 수 차이가 L이상 R 이하일 경우

국경을 열어 열린 국가들끼리 인구 수를 평균으로 맞춰버리는 문제이다

왼->오 변화

처음에는 문제 접근을 모든 좌표에서 루프를 돌되 각 좌표의 오른쪽, 아래쪽 좌표만 검사하면 되지 않을까?

했는데 안되더라

그래서 그냥 상하좌우 다 검사했다!! ^^

 

 

열심히 푼 흔적ㅎㅎ

자세히 보면 BFS문제이당

func함수(인접한 좌표의 인구 차이가 L이상 R이하인지 검사)와 safe함수(이동 가능한지)를 이용햇다

 

예제입력 4번과 5번에 대한 예시는 다음과 같다

예제 4번은 5<=인구 차<=10

예제 5번은 10 <= 인구 차<= 50

이므로 각각 2번, 3번만에 인구 이동이 종료된다

 

인구 이동의 종료는 더이상 BFS할 칸이 없을때이다!!

 

풀이 코드 : 

#include <cstdio>
#include <string.h>
#include <queue>
#include <stack>
#define abs(x) ((x)>0?(x):(-(x)))
using namespace std;
typedef struct {
	int x, y;
}point;
queue<point> q;
stack<point> s;
int n, a[51][51], l, r, dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 }, ans;
bool visit[51][51], b = true;
bool func(int a, int b) {
	return abs(a - b) >= l && abs(a - b) <= r;
}
bool safe(int x, int y) {
	return x >= 0 && x < n && y >= 0 && y < n && !visit[y][x];
}
int main() {
	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]);

	while (b) {
		memset(visit, false, sizeof(visit));
		b = false;
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++) {
				if (visit[i][j])continue;
				if (!(
					(func(a[i][j], a[i + 1][j]) && safe(j, i + 1))
					|| (func(a[i][j], a[i][j + 1]) && safe(j + 1, i))
					))continue;

				int sum = 0, con = 0; b = true;

				visit[i][j] = 1; q.push({ j,i });
				sum += a[i][j]; con++;
				s.push({ j,i });
				while (!q.empty()) {
					point cur = q.front(); q.pop();
					for (int k = 0, nx, ny; k < 4; k++) {
						nx = cur.x + dx[k], ny = cur.y + dy[k];
						if (safe(nx, ny) && func(a[cur.y][cur.x], a[ny][nx])) {
							visit[ny][nx] = 1;
							q.push({ nx,ny });
							sum += a[ny][nx], con++;
							s.push({ nx,ny });
						}
					}
				}
				while (!s.empty()) {
					point cur = s.top(); s.pop();
					a[cur.y][cur.x] = sum / con;
				}
			}
		ans++;
	}
	printf("%d", ans-1);
	return 0;
}

시간복잡도 : O(N^4)

N*N의 좌표를 모두 BFS 검사를 했으니 N*N*N*N라고 볼 수 있다 ... N이 50 이하의 작은 수여서 다행이다 ^-^