[백준] 16234 인구이동

 

숫자 제한들이 아주 작아서 그냥 제한 생각안하고 돌려도 잘 풀리는 문제다!

 

일단 인구이동을 어떻게 시킬지 생각해보자

간단하게 DFS를 이용하면 된다

 

나와 인접한 마을중 인구수 차이가 L이상 R 이하라면 그곳의 인구를 더해주고 체크해주자

이렇게 내가 갈 수 있는 마을의 모든 인구를 더하고 순서를 order에 담아 기억해주자

 

그럼 dfs가 끝나고 인구의 총 합 / 탐색한 마을로

order를 통해 사이좋게 나눠가지면 된다

 

이걸 언제까지해야할까

그냥 이동 할 일이 없을때까지 해보자!

 

이동이 없을 조건은 나 자신만 탐색하고 끝나는 경우다

그걸 cnt의 수가 1이하라면 안하는걸로 했다!

 

쉽게 생각하고 생각없이 짜면 잘 풀린다..!

 

소스코드

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
 
public class Main {
    public static int n,l,r;
    public static int[][] arr;
    public static boolean[][] check;
    public static int cnt,sum;
    public static int[] order;
    public static int[] dx = {0,0,-1,1};
    public static int[] dy = {1,-1,0,0};
    public static boolean inner(int x,int y) {
        return (0<= x && x<n && 0<=y && y<n);
    }
    public static void dfs(int x,int y) {
        check[x][y]=true;
        order[cnt++]=x*n+y;
        sum+=arr[x][y];
        for(int i=0;i<4;i++) {
            int nx = x+dx[i];
            int ny = y+dy[i];
            if(inner(nx,ny) && !check[nx][ny]) {
                int diff = Math.abs(arr[x][y]-arr[nx][ny]);
                if(l<=diff && diff<=r) dfs(nx,ny);
            }
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        l = sc.nextInt();
        r = sc.nextInt();
        arr = new int[n+1][n+1];
        check = new boolean[n+1][n+1];
        order = new int[n*n+5];
        
        for(int i=0;i<n;i++) {
            for(int j=0;j<n;j++) {
                arr[i][j]=sc.nextInt();
            }
        }
        int ans=0;
        while(true) {
            boolean used=false;
            for(int i=0;i<n;i++) {
                for(int j=0;j<n;j++) {
                    if(!check[i][j]) {
                        sum=0; cnt=0;
                        dfs(i,j);
                        if(cnt<=1) continue;
                        used=true;
                        sum/=cnt;
                        for(int k=0;k<cnt;k++) {
                            int x = order[k]/n;
                            int y = order[k]%n;
                            arr[x][y]=sum;
                        }
                    }
                }
            }
            if(!used) break;
            for(int i=0;i<n;i++) {
                for(int j=0;j<n;j++) {
                    check[i][j]=false;
                }
            }
            ans++;
        }
        System.out.println(ans);
    }
}