[Java] 백준 16234번 : 인구 이동

1. 문제

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

16234번: 인구 이동

 

 

2. 풀이 과정

1. dfs 탐색으로 해당 구역과 어느 구역이 연합을 맺었는지 구한다. 이때, 연합을 맺은 구역의 좌표와 인구 수의 합을 저장해둔다.

2. 연합 하나를 구할 때마다, 각 구역의 인구수를 (연합의 인구합)/(연합 구역 수)로 업데이트 해준다.

3. boolean값으로 연합을 찾았는지 확인하며, 연합이 없을 경우 반복문을 종료한다.

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

public class Main {
    static int N, L, R, map[][], total;
    static int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
    static boolean visited[][];
    static ArrayList<int[]> pos;

    public static void findUnion(int x, int y){
        pos.add(new int[]{x, y});
        total += map[x][y];

        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx<0 || nx>=N || ny<0 || ny>=N || visited[nx][ny]){ continue;}
            int gap = Math.abs(map[x][y] - map[nx][ny]);
            if(L<=gap && gap<=R){
                visited[nx][ny] = true;
                findUnion(nx, ny);
            }
        }
    }

    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());
        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());
            }
        }
        //
        int result = -1;
        while(true){
            result++;
            visited = new boolean[N][N];
            boolean done = false;

            for(int i=0; i<N; i++){
                for(int j=0; j<N; j++){
                    if(visited[i][j]){ continue;}
                    total = 0;
                    pos = new ArrayList<>();
                    visited[i][j] = true;
                    findUnion(i, j);
                    if(pos.size() > 1){
                        done = true;
                        int su = total/pos.size();
                        for(int[] region : pos){
                            map[region[0]][region[1]] = su;
                        }
                    }
                }
            }
            if(!done){break;}
        }
        System.out.println(result);
    }
}

 

 

결과