[java 백준] 골드 5/ 16234번 인구이동

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

16234번: 인구 이동

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
class Main{
 
 
    public static int n;
    public static int l;
    public static int r;
    public static int arr[][];
    public static boolean visit[][];
    public static int dirX[]={-1,1,0,0};
    public static int dirY[]={0,0,-1,1};
    public static int ans=0;
 
    public static class Node{
        int x,y;
        public Node(int x,int y){
            this.x=x;
            this.y=y;
        }
    }
 
    public static boolean check(int x,int y,int nx,int ny){
 
        int sub=Math.abs(arr[x][y]-arr[nx][ny]);
        if(sub>=l&&sub<=r){
            return true;
        }
 
 
        return false;
    }
 
 
 
    public static int move(){
        int unionCount=0;
        int unionSize=0;
 
        //탐색
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(!visit[i][j]){
 
 
                    Queue<Node> queue=new LinkedList<Node>();
                    ArrayList<Node>list=new ArrayList<Node>();
                    queue.add(new Node(i,j));
                    list.add(new Node(i,j));
                    unionCount=arr[i][j];
                    visit[i][j]=true;//중요!
 
                    while(!queue.isEmpty()){
                        Node node=queue.poll();
                        for(int s=0;s<4;s++){
                            int nx=node.x+dirX[s];
                            int ny=node.y+dirY[s];
                            if(nx>=0&&nx<n&&ny>=0&&ny<n){
                                if(!visit[nx][ny]&&check(node.x,node.y,nx,ny)){
                                    queue.add(new Node(nx,ny));
                                    list.add(new Node(nx,ny));
                                    visit[nx][ny]=true;
                                    unionSize++;
                                    unionCount+=arr[nx][ny];
                                }
                            }
                        }
                    }
                    //평균값으로 채워주기
                    if(unionSize>0){
                        int avg=unionCount/list.size();
                        for(Node node:list){
                            arr[node.x][node.y]=avg;
                        }
                    }
                }
            }
        }
 
 
 
        //다 false로 바꿔주기
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                visit[i][j]=false;
            }
        }
 
 
        return unionSize;
 
    }
 
    public static void main(String[]args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());
        n=Integer.parseInt(st.nextToken());
        l=Integer.parseInt(st.nextToken());
        r=Integer.parseInt(st.nextToken());
        arr=new int[n][n];
        visit=new boolean[n][n];
        for(int i=0;i<n;i++){
            st=new StringTokenizer(br.readLine());
            for(int j=0;j<n;j++){
                arr[i][j]=Integer.parseInt(st.nextToken());
            }
        }
 
 
 
        boolean isFlag=true;
        while(isFlag){
            if(move()==0){
                isFlag=false;
            }else{
                ans++;
            }
        }
 
        System.out.println(ans);
 
 
 
 
    }
}

 

 

생각의 절차가 3가지가 필요한데

 

1. 인구이동 횟수를 while로 구현 (더이상 이동 못할때까지 반복문 돌려주기)

2. bfs를 통해 인접하고 범위에 들어오는 숫자의 위치를 queue,arraylist에 넣기

3. 평균을 구해서 큐에 있는 숫자들의 위치에 평균값을 넣어주기

 

이다.

 

특히 인구이동횟수는 move함수에서 BFS를 돌면서 unionSize 값이  0이면 더이상 탐색할게 없다는 것이니 반복문을 끊어주면 되는것을 생각해줘야 한다.

그리고 visit잘 확인해야한다. 이거때문에 재귀가 깊어진다.