16234. 인구 이동

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

16234번: 인구 이동

<JAVA>

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

class Main {

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

	public static void main(String[] args) throws Exception {
		class pos {
			pos(int x, int y) {
				this.x = x;
				this.y = y;
			}

			int x, y;
		}
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int N = Integer.parseInt(st.nextToken(" "));
		int L = Integer.parseInt(st.nextToken(" "));
		int R = Integer.parseInt(st.nextToken(" "));
		int cnt = 0, sum = 0;
		int map[][] = new int[N][N];
		boolean visit[][] = new boolean[N][N];
		List<pos> list = new ArrayList<>();
		Queue<pos> q = new LinkedList<>();
		for (int i = 0; i < N; ++i) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < N; ++j) {
				map[i][j] = Integer.parseInt(st.nextToken(" "));
			}
		}
		boolean isUpdate = true; // 인구 이동 여부 확인
		while (isUpdate) {
			isUpdate = false;
			visit = new boolean[N][N];
			// BFS
			for (int i = 0; i < N; ++i) {
				for (int j = 0; j < N; ++j) {
					if (!visit[i][j]) {
						sum = 0;
						visit[i][j] = true;
						sum += map[i][j];
						q.add(new pos(i, j));
						list.add(new pos(i, j));
						while (!q.isEmpty()) {
							pos cur = q.poll();
							for (int dir = 0; dir < 4; ++dir) {
								int nx = cur.x + dx[dir];
								int ny = cur.y + dy[dir];
								if (nx < 0 || nx >= N || ny < 0 || ny >= N || visit[nx][ny]
										|| Math.abs(map[nx][ny] - map[cur.x][cur.y]) < L
										|| Math.abs(map[nx][ny] - map[cur.x][cur.y]) > R)
									continue;
								sum += map[nx][ny];
								visit[nx][ny] = true;
								q.add(new pos(nx, ny));
								list.add(new pos(nx, ny));
								isUpdate = true;
							}
						}
						sum /= list.size();
						for (int k = 0; k < list.size(); ++k) {
							map[list.get(k).x][list.get(k).y] = sum;
						}
						list.clear();
					}
				}
			}
			if (isUpdate) {
				++cnt;
			}
		}
		System.out.println(cnt);
	}
}

<C++>

#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
const int dx[] = { 1, -1, 0, 0 };
const int dy[] = { 0, 0, 1, -1 };

int map[50][50];
bool visit[50][50];
int N, L, R, cnt, sum;
struct pos
{
	int x, y;
};
vector<pos> v;
queue <pos> q;
int main()
{
	cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
	cin >> N >> L >> R;
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			cin >> map[i][j];
		}
	}

	bool isUpdate = true;	// 인구 이동 여부 확인
	while (isUpdate)
	{
		isUpdate = false;
		memset(visit, false, sizeof(visit));
		// BFS
		for (int i = 0; i < N; ++i)
		{
			for (int j = 0; j < N; ++j)
			{
				if (!visit[i][j])
				{
					sum = 0;
					visit[i][j] = true;
					sum += map[i][j];
					q.push({ i,j });
					v.push_back({ i,j });
					while (!q.empty())
					{
						pos cur = q.front(); q.pop();
						for (int dir = 0; dir < 4; ++dir)
						{
							int nx = cur.x + dx[dir];
							int ny = cur.y + dy[dir];
							if (nx < 0 || nx >= N || ny < 0 || ny >= N || visit[nx][ny] || abs(map[nx][ny] - map[cur.x][cur.y]) < L || abs(map[nx][ny] - map[cur.x][cur.y]) > R)
								continue;
							sum += map[nx][ny];
							visit[nx][ny] = true;
							q.push({ nx,ny });
							v.push_back({ nx,ny });
							isUpdate = true;
						}
					}
					sum /= v.size();
					for (int k = 0; k < v.size(); ++k)
					{
						map[v[k].x][v[k].y] = sum;
					}
					v.clear();
				}
			}
		}
		if (isUpdate)
		{
			++cnt;
		}
	}
	cout << cnt;
	return 0;
}