[백준 16234] 인구이동

# 문제링크

www.acmicpc.net/problem/16234

16234번: 인구 이동

국경선을 공유하는 두 나라라고 해서 바로 BFS를 떠올렸다. Floodfill 처럼 가능한 부분을 쫘악 탐색해서 평균값으로 바꿔주면 된다.. 탐색이 더이상 진행되지 않으면 끝내고 답을 제출한다..

 

처음에는 인구이동을 탐색이 끝나고 한 번에 진행하려고, 해당 정보들을 배열에 담아뒀었다. 근데 그렇게 하니까 배열을 한 번 더 돌아야 하는 단점도 있고, 정확하지 않아져서 (..??) 자꾸 틀렸다. ㅠㅠ 구글신의 도움으로 queue를 활용하여 바로바로 map을 바꾸는 방법을 택했다. 얌문님 만세..

 

시험장에서는 구글신을 못쓸텐데 걱정이 된다.. 

 

# 제출 코드 

 

#include <cstdio>
#include <queue>
#include <cstdlib>
#include <cstring>
using namespace std;

int map[51][51];
int N, L, R;
bool visited[51][51];

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", &map[i][j]);
		}
	}
}

int xd[] = { 1, -1, 0,0 };
int yd[] = { 0, 0,1, -1 };

bool BFS(int y, int x) {
	queue <pair<int, int>> q;
    queue <pair<int, int>> mv;
	int sum = map[y][x];
	visited[y][x] = true; // 시작
	q.push({ y,x });
    mv.push({ y,x });

	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int ny = y + yd[i];
			int nx = x + xd[i];

			if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
			if (visited[ny][nx] == true) continue;
			int tmp = abs(map[ny][nx] - map[y][x]); // 두 나라의 차이 
			if (L > tmp || tmp > R) continue;

			visited[ny][nx] = true;
			sum += map[ny][nx];
			q.push({ ny,nx });
            mv.push({ ny,nx });
		}
	}

	int avg = sum / mv.size();
    if (mv.size() == 1) { 
        mv.pop();
        return false; 
    }
    while (!mv.empty()) {
        int y = mv.front().first;
        int x = mv.front().second;
        mv.pop();
        map[y][x] = avg;
    }
	return true;
}

int Solve() {
	int ans = 0;
	bool flag = true;
	while (true) {
		flag = false;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (visited[i][j] == 0) {
					if (BFS(i, j)) flag = true;
				}
			}
		}
		if (!flag) break;
		ans++;
		memset(visited, 0, sizeof(visited));
	}
	return ans;
}
int main() {
	Input();
	printf("%d", Solve());
	return 0;
}