[백준] 16234 인구이동

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main16234_bj_인구이동 {
	static int N, L, R;
	static int[][] country;
	static int[] di = { 0, 1, 0, -1 };
	static int[] dj = { 1, 0, -1, 0 };
	static boolean[][] select;
	static Queue<Point> queue;
	static Queue<Point> ansQeueu;
	static int ni, nj;
	static int cnt, sum;
	
	static boolean check(int i, int j) {
		if (i >= 0 && i < N && j >= 0 && j < N)
			return true;
		else
			return false;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		N = sc.nextInt();
		L = sc.nextInt();
		R = sc.nextInt();

		country = new int[N][N];
		queue = new LinkedList<>();
		ansQeueu = new LinkedList<>();

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				country[i][j] = sc.nextInt();
			}
		}
		/////////////////////// 입력
		
		
		int ans = 0; // 출력값 저장 변수
		
		while(true) {
			select = new boolean[N][N]; // 이동 후 국경선을 열 나라를 확인하기 위해 다시 false로 초기화
			boolean flag = false; // 이동이 일어났는지 판별할 변수
			
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if(!select[i][j]) { // 이동이 이미 일어난 나라면 pass
						queue.add(new Point(i, j)); // 일단 국경을 열 것이라 예상, queue에 넣고 true로 변경해준다
						select[i][j] = true; 
						sum = cnt = 0; // 국경선 여는 나라의 인구 수 저장, 몇개의 나라인지 count
						bfs();
						
						if(cnt > 1) {
							flag = true;
							int diff = sum / cnt;
							while(!ansQeueu.isEmpty()) {
								Point tmp = ansQeueu.poll();
								country[tmp.i][tmp.j] = diff;
							}
						}else {
							select[i][j] = false;
							ansQeueu.clear();
						}
					}
				}
			}
			if(flag) ans++;
			if(!flag) break;
		}
		System.out.println(ans);
	}
	

	static void bfs() {
		while(!queue.isEmpty()) {
			Point now = queue.poll();
			ansQeueu.add(now); // 국경선을 공유하는 나라를 저장할 queue
			int nowValue = country[now.i][now.j];
			sum += nowValue;
			cnt++;
			for (int d = 0; d < 4; d++) {
				ni = di[d] + now.i;
				nj = dj[d] + now.j;
				
				if(check(ni, nj) && !select[ni][nj] && (Math.abs(nowValue - country[ni][nj]) >= L) &&
						(Math.abs(nowValue - country[ni][nj]) <= R)) {
					// 이 나라와 공유하는 나라가 있는지 확인하기위해 queue가 아닌 ansQueue에 저장한다. 
					queue.add(new Point(ni, nj));
					select[ni][nj] = true; // 이미 공유하고 있는 나라와의 중복을 제거하기 위해 true로 바꿔준다.
				}
			}
		}
	}
	
	static class Point {
		int i, j;
		
		public Point(int i, int j) {
			this.i = i;
			this.j = j;
		}
	}
}