백준 16234_인구 이동_JAVA

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

 

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

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

    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()); // 최대 차이

        grid = new int[N][N];

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

        System.out.println(move());
    }

    public static int move() { // 더 이상 인구이동이 일어나지 않을 때까지 반복
        int result = 0;
        boolean isMove = true;
        while (isMove) {
            isMove = false;
            visited = new boolean[N][N];
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (!visited[i][j]) {
                        int sum = bfs(i, j);
                        // 인구 이동이 가능한 경우 각 지점의 인구를 업데이트
                        if (arr.size() > 1) {
                            isMove = true;
                            int avg = sum / arr.size();
                            for (int[] pos : arr) {
                                grid[pos[0]][pos[1]] = avg;
                            }
                        }
                    }
                }
            }
            if (isMove) {
                result++;
            }
        }
        return result;
    }

    private static int bfs(int x, int y) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{x, y});
        int peopleSum = 0;
        arr = new ArrayList<>();
        arr.add(new int[]{x, y});
        visited[x][y] = true;

        peopleSum += grid[x][y];

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int cx = cur[0];
            int cy = cur[1];

            for (int i = 0; i < 4; i++) {
                int nx = cx + dx[i];
                int ny = cy + dy[i];

                if (nx >= 0 && ny >= 0 && nx < N && ny < N && !visited[nx][ny]) {
                    int difference = Math.abs(grid[nx][ny] - grid[cx][cy]);
                    if (difference >= L && difference <= R) {
                        queue.add(new int[]{nx, ny});
                        arr.add(new int[]{nx, ny});
                        peopleSum += grid[nx][ny];
                        visited[nx][ny] = true;
                    }
                }
            }
        }
        return peopleSum;
    }
}

 

 

- 회고

- 풀이 과정은 다 맞았는데 마지막 while문 회전 횟수를 세는 조건을 구현하지 못해 결국 블로그를 참고했다.

- 생각보다 쉽지 않으면서도 할만하다고 느꼈다.