[삼성기출]백준16234 - 인구이동

import java.io.*;
import java.util.*;

public class Main16234_인구이동 {
	
	static int N,L,R;
	static int[][] map;
	static boolean[][] visit;
	static int[][] dir = // 우,하,좌,상; 
    
	static boolean check(int x, int y) {
		if(x>=0 && x<map.length && y>=0 && y<map[x].length)
			return true;
		else return false;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] input = br.readLine().trim().split(" ");
		N = Integer.parseInt(input[0]);
		L = Integer.parseInt(input[1]);
		R = Integer.parseInt(input[2]);
		map = new int[N][N];
		for(int i=0; i<N; i++) {
			String[] str = br.readLine().trim().split(" ");
			for(int j=0; j<N; j++) {
				map[i][j] = Integer.parseInt(str[j]);
			}
		}
		int res = 0;
		/*
		 * 최대 2000번까지 이동체크.
		 */
		for(int i=1; i<=2000; i++) {
			visit = new boolean[N][N];
			if(!move()) { // 이동할 수 없으면 이전 값 리턴. 
				res = i-1;
				break;
			}
		}
		System.out.println(res);
	}
	
	
	public static boolean move() {
		int cnt = 0;
		for(int i=0; i<map.length; i++) {
			for(int j=0; j<map[i].length; j++) {
				if(!visit[i][j] && union(i,j)) cnt++;
			}
		}
		return cnt>0?true:false; // 한번이라도 이동했으면 true
	}
	static class Pos{
		int x,y;

		public Pos(int x, int y) {
			this.x = x;
			this.y = y;
		}

		@Override
		public String toString() {
			return "[" + x + "," + y + "]";
		}
		
	}
	public static boolean union(int x, int y) {
		/*
		 * 시작점으로 부터 bfs로 연합하고 인구수 나누기.
		 */
		boolean flag = false;
		Queue<Pos> qu = new LinkedList<>();
		List<Pos> list = new ArrayList<>();
		Pos p = new Pos(x,y);
		qu.add(p);
		list.add(p);
		visit[p.x][p.y]=true;
		int dx,dy;
		int sum = 0;
		Pos tmp = null;
		while(!qu.isEmpty()) {
			p = qu.poll();
			sum += map[p.x][p.y];
			for(int d=0; d<4; d++) {
				dx = p.x + dir[d][0];
				dy = p.y + dir[d][1];
				if(check(dx,dy) && !visit[dx][dy] && checkDistance(p.x,p.y,dx,dy)) {
					tmp = new Pos(dx,dy);
					qu.add(tmp);
					list.add(tmp);
					visit[dx][dy]=true;
					flag = true;
				}
			}
		}
		
		// 우리 국가 이외에 다른 국가도 있으면 계산.
		if(list.size()>1) {
			int dis = sum/list.size();
			for(int i=0; i<list.size(); i++) {
				map[list.get(i).x][list.get(i).y] = dis;
			}
		}
		return flag;
	}
	
	// 인접한 국가와의 인구차이로 연합할 수 있는지 체크.
	static boolean checkDistance(int x1, int y1, int x2, int y2) {
		int dis = Math.abs(map[x1][y1] - map[x2][y2]);
		if(dis >=L && dis <= R)
			return true;
		else return false;
	}
	
	public static void print() {
		for(int i=0; i<map.length; i++) {
			for(int j=0; j<map[i].length; j++)
				System.out.print(map[i][j]+" ");
			System.out.println();
		}
		System.out.println("======================");
	}
}