[알고리즘] 백준 16234 인구 이동 - JAVA

www.acmicpc.net/problem/16234

16234번: 인구 이동

문제 설명

상하좌우로 인접해 있는 땅과의 인구수 차이가 L이상 R이하면 국경선이 열린다.

 

인접한 땅만을 통해서 형성된 그룹을 연합이라 한다. (BFS 또는 DFS를 통해서 탐색이 되는 범위)

 

연합 내의 모든 나라는 동일한 인구수를 가지도록 사람들을 이주시킨다. (소수점 제외)

 

인구 이동을 더 이상 할 수 없을 때까지 사람들을 이주 시켜야 할 때, 총 몇번의 인구 이동이 이루어질지를 구하는 문제이다.

 

풀이 과정

연합을 형성하는 방법과 인구 이동에 대한 기준을 생각하는게 포인트라고 본다.

 

연합을 형성하는 방법은 BFS와 DFS 아무거나 사용해도 상관이 없다.

 

인구 이동의 횟수에 대한 기준은 (0, 0)부터 시작하여 (N - 1, N - 1)까지 모든 땅에 대하여 연합을 형성하고 인구를 이주시키는 것을 한 번의 인구 이동으로 봐야한다. 

 

인구를 1번 이주시키더라도 인구수가 변경됨에 따라 열리지 않던 국경이 열리는 경우가 존재한다.

 

더 이상 인구이동이 이루어지지 않으려면 반복문을 계속 돌리면서 특정 Flag를 세우는 방법 등을 세워 횟수가 정해지지 않은 반복문을 수행해야한다.

 

자세한 구현 내용은 주석에서 설명하겠다.

 

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Main {

    static int N;
    static int L;
    static int R;
    static int[][] map;
    static final int[] dx = {0, 0, -1, 1};
    static final int[] dy = {1, -1, 0, 0};

    static boolean[][] visited;

    public static void main(String[] args) throws IOException {

        // input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        StringTokenizer st = new StringTokenizer(s, " ");

        N = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());
        map = new int[N][N];
        visited = new boolean[N][N];

        for (int i = 0; i < N; i++) {
            s = br.readLine();
            st = new StringTokenizer(s, " ");

            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        // input end

        int result = 0; // 인구 이동 횟수
        boolean flag = true; // 반복문 탈출 flag

        while (flag) {
            if (movePeople() == 0) // 더 이상 인구 이동을 할 수가 없으면 반복문 탈출
                flag = false;
            else
                result++;
        }

        System.out.println(result);
    }

    // BFS를 통해 그룹을 형성한다.
    // 연합이 형성되었으면 인구를 동일하게 분배한다.
    static int movePeople() {
        int unionCount = 0; // 연합이 형성될 수 있으면 무조건 0 이상의 값을 가짐

        // (0,0) ~ (N-1,N-1)까지 BFS 수행
        for (int x = 0; x < N; x++) {
            for (int y = 0; y < N; y++) {
                if (!visited[x][y]) {
                    Queue<Location> queue = new LinkedList<>();
                    Location location = new Location(x, y);
                    queue.add(location);

                    List<Location> list = new ArrayList<>();
                    list.add(location);

                    visited[location.x][location.y] = true;

                    int unionSum = map[location.x][location.y]; // 인구의 합계

                    while (!queue.isEmpty()) {
                        Location current = queue.poll();

                        for (int i = 0; i < 4; i++) {
                            int nx = current.x + dx[i];
                            int ny = current.y + dy[i];

                            if (nx >= 0 && nx < N && ny >= 0 && ny < N) {
                                if (!visited[nx][ny] && checkBoundary(current.x, current.y, nx, ny)) {
                                    queue.add(new Location(nx, ny));
                                    list.add(new Location(nx, ny));
                                    visited[nx][ny] = true;
                                    unionCount++;
                                    unionSum += map[nx][ny];
                                }
                            }
                        }
                    }

                    // 연합이 형성되었다면 unionCount는 무조건 0이상
                    // 연합에 인구를 똑같이 분배한다.
                    if (unionCount > 0) {
                        int aver = unionSum / list.size();

                        for (int i = 0; i < list.size(); i++) {
                            Location current = list.get(i);
                            map[current.x][current.y] = aver;
                        }
                    }
                }
            }
        }

        // 다음 인구 이동을 위해 visited 배열을 모두 false 값으로 함
        for (int i = 0; i < N; i++) {
            Arrays.fill(visited[i], false);
        }

        return unionCount;
    }

    // 인접한 땅과 인구수 비교
    // L 이상 R 이하면 참 반환
    static boolean checkBoundary(int cx, int cy, int nx, int ny) {
        int sub = Math.abs(map[cx][cy] - map[nx][ny]);

        if (sub >= L && sub <= R)
            return true;

        return false;
    }

    // 좌표
    static class Location {
        int x;
        int y;

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

}