[BOJ] 16234. 인구이동

import java.util.*;

public class Main {
	public static int N, L, R;
	public static int day = 0;
	public static int[][] map;
	public static int[][] group;
	public static int[] dy = {1, 0, -1, 0};
	public static int[] dx = {0, 1, 0, -1};

	public static void bfs(int y, int x, int groupCnt) {
		ArrayList<Point> list = new ArrayList<>();
		Queue<Point> q = new LinkedList<>();
		q.add(new Point(y, x));
		group[y][x] = groupCnt;
		int sum = map[y][x];
		int cnt = 1;
		list.add(new Point(y, x));

		while (!q.isEmpty()) {
			Point p = q.poll();
			for (int i = 0; i < 4; i++) {
				int ny = p.y + dy[i];
				int nx = p.x + dx[i];
				if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
				if(group[ny][nx] == -1) {
					int dif = Math.abs(map[ny][nx] - map[p.y][p.x]);
					if (L <= dif && dif <= R) {
						q.add(new Point(ny, nx));
						group[ny][nx] = groupCnt;
						sum += map[ny][nx];
						cnt++;
						list.add(new Point(ny, nx));
					}
				}
			}
		}

		for (int i = 0; i < list.size(); i++) {
			y = list.get(i).y;
			x = list.get(i).x;
			map[y][x] = sum / cnt;
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		L = sc.nextInt();
		R = sc.nextInt();
		map = new int[N][N];
		group = new int[N][N];
        
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				map[i][j] = sc.nextInt();
			}
		}

		while (true) {
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					group[i][j] = -1;
				}
			}
			int groupCnt = 0;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (group[i][j] == -1) {
						bfs(i, j, groupCnt);
						groupCnt++;
					}
				}
			}
			if (groupCnt == N * N) break;
			day++;
		}
		System.out.println(day);
	}

	static class Point {
		public int y, x;
		
		public Point(int y, int x) {
			this.y = y;
			this.x = x;
		}
	}
}

import java.util.*;

public class Main {
	public static int N, L, R;
	public static int day = 0;
	public static int[][] map;
	public static int[][] check;
	public static int[] dy = {1, 0, -1, 0};
	public static int[] dx = {0, 1, 0, -1};

	public static void bfs(int y, int x) {
		ArrayList<Point> list = new ArrayList<>();
		Queue<Point> q = new LinkedList<>();
		q.add(new Point(y, x));
		check[y][x] = 1;
		int sum = map[y][x];
		int cnt = 1;
		list.add(new Point(y, x));

		while (!q.isEmpty()) {
			Point p = q.poll();
			for (int i = 0; i < 4; i++) {
				int ny = p.y + dy[i];
				int nx = p.x + dx[i];
				if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
				if(check[ny][nx] == 0) {
					int dif = Math.abs(map[ny][nx] - map[p.y][p.x]);
					if (L <= dif && dif <= R) {
						q.add(new Point(ny, nx));
						check[ny][nx] = 1;
						sum += map[ny][nx];
						cnt++;
						list.add(new Point(ny, nx));
					}
				}
			}
		}

		for (int i = 0; i < list.size(); i++) {
			y = list.get(i).y;
			x = list.get(i).x;
			check[y][x] = sum / cnt;
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		L = sc.nextInt();
		R = sc.nextInt();
		map = new int[N][N];
		check = new int[N][N];
        
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				map[i][j] = sc.nextInt();
			}
		}

		while (true) {
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (check[i][j] == 0) {
						bfs(i, j);
					}
				}
			}
			if(compareMap()) break;
			else day++;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					map[i][j] = check[i][j];
					check[i][j] = 0;
				}
			}
		}
		System.out.println(day);
	}
	
	static boolean compareMap() {
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				if(map[i][j] != check[i][j]) return false;
			}
		}
		return true;
	}

	static class Point {
		public int y, x;
		
		public Point(int y, int x) {
			this.y = y;
			this.x = x;
		}
	}
}