16234-인구이동

 

package com.exam;

import java.util.*;

public class B16234 {
    static final int MAX_N = 10;
    static int n,l,r, result;
    static int[][] Board = new int[MAX_N][MAX_N];
    static int[][] D = {{-1,0},{1,0},{0,-1},{0,1}};
    static ArrayList<Node> union;
    static Queue<Node> queue;
    static boolean[][] visited;

    static class Node{
        int col,row=0;
        Node(int row, int col){
            this.row=row;
            this.col=col;
        }
    }
    public static int move(){
        while(true) {
        	// 해당 노드에 방문했는지 확인하기위해
            visited = new boolean[n][n];
          	// 인구변경이 일어났는지 확인하기위해
            boolean isMove = false;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {

                    if (!visited[i][j]) {
                        int avg = bfs(i, j);
                        if (avg == -1) {
                            continue;
                        }
                        if (union.size() > 1) {
                            setAvg(avg);
                            isMove = true;
                        }
                    }
                }
            }if(!isMove) return result;
            //인구변경이 일어났으면 ++
            result ++;
        }
    }
    public static void setAvg(int avg){
        for(Node node : union){
        	//해당 연합에 해당하는 국가들의 인구 평균 구하기
            Board[node.row][node.col] = avg;
        }
    }

    public static int bfs(int sRow, int sCol){
        queue = new LinkedList<>();
        visited[sRow][sCol] = true;
        queue.add(new Node(sRow,sCol));
        
        // 연합에 node정보 담기
        union = new ArrayList<>();
        union.add(new Node(sRow,sCol));

        int sum = Board[sRow][sCol];

        while(!queue.isEmpty()){
            Node curr = queue.remove();
            for(int i=0; i<4; i++){
            	// 해당 노드의 상하좌우 탐색 
                int nr = curr.row+D[i][0];
                int nc = curr.col+D[i][1];
				// 만약 범위 밖이거나 이미 방문했으면 건너뛰기
                if(nr<0 || nr>n-1 || nc<0 || nc>n-1)continue;
                if(visited[nr][nc])continue;
                int minus = Math.abs(Board[curr.row][curr.col]-Board[nr][nc]);
                // 노드와 탐색노드 차가 입력한 범위내면
                if(minus>=l && minus<=r){
                	//방문등록 후 큐와 연합에 정보 담기
                    visited[nr][nc] = true;
                    queue.add(new Node(nr,nc));
                    union.add(new Node(nr,nc));
                    sum += Board[nr][nc];
                }
            }
        }
        if(union.size()>1) {
            return sum / union.size();
        }else{
            return -1;
        }
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        l = sc.nextInt();
        r = sc.nextInt();
        Board = new int[n][n];
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                Board[i][j] = sc.nextInt();
            }
        }
        System.out.println(move());
    }
}