문제

풀이

1. map이란 2차원 배열에는 인구수들이 저장
2. 0,0부터 n-1,n-1까지 인구 이동이 일어나는지 while문을 통해 반복 확인
3. 인구 이동은 bfs를 통해 진행한다.
4. 인구 이동이 일어나지 않으면 while문 종료

• bfs함수에서 인구 이동이 일어나면 true를 반환 한번이라도 true가 반환이 되면 canContinue 변수를 통해 while문을 한번 더 진행하도록 했다.

코드

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

public class Main {
    static int n,l,r;
    static int[][] map,v;
    static int[][] d=new int[][]{{0,-1},{0,1},{-1,0},{1,0}};

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

        map=new int[n][n];
        for(int i=0;i<n;i++){
            st=new StringTokenizer(br.readLine());
            for(int j=0;j<n;j++){
                map[i][j]=Integer.parseInt(st.nextToken());
            }
        }

        boolean end=false;
        int ans=-1;
        while(!end){
            ans++;
            v=new int[n][n];
            boolean canContinue=false;
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    if(v[i][j]==0){
                        boolean ret=bfs(i,j);
                        if(ret)canContinue=true;
                    }
                }
            }
            if(!canContinue)end=true;
        }
        System.out.println(ans);

    }

    static boolean bfs(int y,int x){
        Queue<Pos> q=new LinkedList<>();
        q.add(new Pos(y,x));
        v[y][x]=1;
        int population=map[y][x];
        int countries=1;
        ArrayList<Pos> list=new ArrayList<>();
        while(!q.isEmpty()){
            Pos now=q.poll();
            list.add(now);
            for(int i=0;i<4;i++){
                int dy=now.y+d[i][0];
                int dx=now.x+d[i][1];
                if(dy<0||dx<0||dy>=n||dx>=n)continue;
                int gap=Math.abs(map[dy][dx]-map[now.y][now.x]);
                if(l<=gap && gap<=r && v[dy][dx]==0){
                    population+=map[dy][dx];
                    countries++;
                    v[dy][dx]=1;
                    q.add(new Pos(dy,dx));
                }
            }
        }
        int newPopul=population/countries;
        for(Pos pos:list){
            map[pos.y][pos.x]=newPopul;
        }
        return list.size() != 1;
    }

    static class Pos{
        int y,x;

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

#구현 #bfs