16234번. 인구 이동

 

아이디어

1. bfs 탐색을 통해 국경이 열리는 국가들을 하나의 연합으로 묶고

2. (연합 총 인구수 / 연합 국가 수) 를 계산하여 연합으로 묶인 국가들의 인구를 갱신해준다.

3. 이 때 기존 인구 수와 갱신해야 하는 인구 수가 같다면 갱신이 불필요 즉 인구 이동이 일어나지 않으므로 인구 갱신 시 '기존 인구 수와 갱신 인구 수가 같지 않을 때만 인구 이동이 일어났다고 판단한다'

 

매일 새로운 visited 배열과 함께 1 ~ 3 과정을 수행하고 3 과정에서 '인구 이동이 없었다' 라고 판단이 되면 다음 날로 넘어가지 않고 현재까지 며칠이 소요되었는지를 출력하면 된다.

 

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

public class _n16234_ {

    static int N;
    static int L;
    static int R;
    static List<int[]> group;

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

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

        /*
        국경선이 open 되는 그룹끼리 묶고,
        각 그룹의 인구 수가 모두 동일하다면 인구 이동 X
        동일하지 않다면 인구 이동 O
         */

        int day = 0;
        while (true) {
            boolean isMove = false;

            boolean[][] visited = new boolean[N][N];
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (!visited[i][j]) {
                        group = new ArrayList<>();
                        int groupPopulation = bfs(i, j, populations, visited);
                        if (move(populations, groupPopulation)) {
                            isMove = true;
                        }
                    }
                }
            }

            if (!isMove) break;
            day++;
        }

        System.out.println(day);
    }

    public static int bfs(int i, int j, int[][] populations, boolean[][] visited) {
        int sum = 0;
        int cnt = 0;

        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{i, j});
        group.add(new int[]{i, j});
        visited[i][j] = true;
        sum += populations[i][j];
        cnt++;

        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};
        while (!queue.isEmpty()) {
            int[] temp = queue.poll();
            int x = temp[0];
            int y = temp[1];

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

                if (nx < 0 || ny < 0 || nx >= N || ny >= N || visited[nx][ny]) continue;

                int diff = Math.abs(populations[x][y] - populations[nx][ny]);
                if (diff < L || diff > R) continue;

                queue.add(new int[]{nx, ny});
                group.add(new int[]{nx, ny});
                visited[nx][ny] = true;
                sum += populations[nx][ny];
                cnt++;
            }
        }

        return sum / cnt;
    }

    public static boolean move(int[][] populations, int groupPopulation) {
        boolean isMoved = false;

        int L = group.size();

        for (int i = 0; i < L; i++) {
            int[] temp = group.get(i);
            int x = temp[0];
            int y = temp[1];

            if (populations[x][y] != groupPopulation) {
                populations[x][y] = groupPopulation;
                isMoved = true;
            }
        }

        return isMoved;
    }
}