백준 16234번 인구 이동

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

16234번: 인구 이동

 

 

 

 

 

 

<접근방법>

bfs 탐색으로 시뮬레이션 하는 문제입니다.

조건을 만족하면 탐색을 계속하고 아니면 종료해야합니다.

 

연합인 나라를 모두 알아낸 후에서야 인구 이동이 시작됩니다.

따라서 탐색 중 연합인 나라를 저장해주고 나중에 인구이동 처리를 해야합니다.

 

 

---

 

 

 

<코드>

#include <iostream>
#include <algorithm>
#include <queue>
#include <memory.h>
using namespace std;

struct point {
	int y, x;
};

int n, L, R;
int map[50][50], visit[50][50];
int res = 0;
int dy[4] = { 1, -1, 0, 0 };
int dx[4] = {0, 0, 1, -1};

queue<point> q;
queue<point> open;

void reset() {
	memset(visit, 0, sizeof(visit));
}

bool bfs(int y, int x) {
	bool suc = false;
	visit[y][x] = 1;
	q.push({ y, x});

	while (!q.empty()) {
		point t = q.front();
		q.pop();

		int val = map[t.y][t.x];
		for (int i = 0; i < 4; i++) {
			int ty = t.y + dy[i];
			int tx = t.x + dx[i];
			int tval = map[ty][tx];

			if (ty < 0 || ty >= n || tx < 0 || tx >= n) continue;
			if (visit[ty][tx] != 0) continue;
			if (L <= abs(val - tval) && abs(val - tval) <= R) {
				suc = true;

				open.push({ ty, tx });
				q.push({ ty, tx });
				visit[ty][tx] = 1;
			}
		}
	}

	if (suc) open.push({y, x});
	return suc;
}

void move() {
	queue <point> tq;

	int sz = open.size();
	int sum = 0;
	while (!open.empty()) {
		point t = open.front();
		open.pop();
		tq.push(t);

		sum += map[t.y][t.x];
	}
	int avg = sum / sz;

	while (!tq.empty()) {
		point t = tq.front();
		tq.pop();

		map[t.y][t.x] = avg;
	}
}

int main() {
	cin >> n >> L >> R;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
		}
	}

	while (1) {
		reset();

		bool found = false;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (visit[i][j] != 0) continue;
				if (bfs(i, j)) {
					move();
				}
			}
		}
		if (!found) res++;
		else break;
	}
	cout << res << '\n';
	return 0;
}

 

 

---

 

 

<느낀 점>

-차이는 절댓값으로!!