문제 바로가기

접근방법

• bfs문제인걸 보자마자 알았음.
• bfs돌면서 l보다 크고 r보다 작은 조건이면 수들을 더해나가며 평균을 구해 해당 인구들을 업데이트시켜주면 되겠다 까지 생각해냄.
• 근데 풀다가 인구이동을 어떻게 멈춰야하는지에 대한 조건을 생각해내는 것이 까다로워 결국 다른 사람들의 코드를 보고 풀었음.
  

핵심

• bfs도는건 알겠는데...언제 인구이동이 멈추는지 알아?
• 바로 boolean타입의 flag를 하나 만들어준다!
• visited되지 않은 땅을 기준으로 bfs도는데, bfs함수 내에 만들어놓은 li(q와 같이 만들었는데 poll하지 않는다는 것이 차이)의 크기가 1보다 크다면 flag를 true로 바꿔준다.
• 모든 땅을 다 검사하고 flag가 true로 바뀌지 않았다면 결과를 return 해준다.

static int move(){
        int cnt=0;

        while(true){
            boolean flag=false;
            v=new boolean[n][n];

            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    if(!v[i][j]){
                        int avg=bfs(i,j);
                        if(li.size()>1){
                            flag=true;
                            update(avg);
                        }
                    }
                }
            }
            if(!flag) return cnt;
            cnt++;
        }
    }

전체코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ_16234 {
    static int n, l, r, avg;
    static int[][] arr;
    static int[] dx={0,0,1,-1};
    static int[] dy={1,-1,0,0};
    static boolean[][] v;
    static ArrayList<int[]> li;

    public static void main(String[] args) throws Exception{
        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];

        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());
            }
        }

        System.out.println(move());
    }

    static int move(){
        int cnt=0;

        while(true){
            boolean flag=false;
            v=new boolean[n][n];

            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    if(!v[i][j]){
                        int avg=bfs(i,j);
                        if(li.size()>1){
                            flag=true;
                            update(avg);
                        }
                    }
                }
            }
            if(!flag) return cnt;
            cnt++;
        }
    }

    static int bfs(int x, int y){
        int sum=arr[x][y];
        Queue<int[]> q=new LinkedList<>();
        li=new ArrayList<>();
        q.add(new int[]{x,y});
        li.add(new int[]{x,y});
        v[x][y]=true;

        while(!q.isEmpty()){
            int[] c=q.poll();
            int cx=c[0];
            int cy=c[1];

            for(int i=0;i<4;i++){
                int nx=cx+dx[i];
                int ny=cy+dy[i];

                if(nx<0||ny<0||nx>=n||ny>=n) continue;
                if(v[nx][ny]) continue;
                if(l<=Math.abs(arr[nx][ny]-arr[cx][cy]) && Math.abs(arr[nx][ny]-arr[cx][cy])<=r){
                    sum+=arr[nx][ny];
                    v[nx][ny]=true;
                    q.add(new int[]{nx,ny});
                    li.add(new int[]{nx,ny});
                }
            }
        }

        avg=sum/li.size();
        return avg;
    }

    static void update(int avg){
        for(int[] l:li){
            int x=l[0];
            int y=l[1];
            arr[x][y]=avg;
        }
    }
}