[백준 JAVA] 16234 인구이동

16234 인구이동

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

문제설명

n x n 격자가 주어지고, 각 격자는 특정 인구 수를 나타낸다.

인구 이동을 시뮬레이션하여 더 이상 이동할 수 없을 때까지 반복한다.

1. 인접한 두 지역 간의 인구 차이가 지정된 범위 [l, r] 내에 있으면, 인구가 이동할 수 있다.
2. 이동이 발생하면 연결된 지역(서로 연결된 지역)의 인구는 평균값으로 조정된다.
3. 더 이상 이동이 일어나지 않을 때까지 며칠이 걸리는지를 계산해야 다.

접근방식

각 BFS는 모든 노드를 방문하게 되어 O(n^2)의 시간이 소요된다.

O(n ^ 2) 의 시간이 소요되는 BFS가 각 셀에 대해 호출된다면 전체 시간 복잡도는 O(n^2 * n^2)가 되어 O(n^4)로 표현된다.

 

문제 조건 분석 과정

• BFS 알고리즘을 이용한 이동 시뮬레이션:
  • 각 셀을 순회하며 이동 가능한지를 체크한다.
  • BFS를 사용해 인구를 공유할 수 있는 연결된 지역을 탐색한다.
• BFS 로직:
  • bfs() 메서드에서 큐를 사용하여 시작 셀과 연결된 모든 지역을 탐색한다.
  • 연결된 지역을 찾으면 인구를 합산하고 해당 좌표를 list에 저장한다.
• 인구 조정:
  • BFS가 완료된 후, 연결된 지역이 2개 이상일 경우 모든 연결된 지역의 인구를 평균값으로 설정한다.
  • 더 이상 이동이 불가능할 때까지 반복한다.

전체코드

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

public class Main {
    static int n, l, r;
    static int[][] board;
    static boolean[][] visited;
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};
    static ArrayList<Node> list;

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

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

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

    public static int move() {
        int result = 0;
        while (true) {
            boolean 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 (list.size() > 1) {
                            changePopulation(sum);
                            isMove = true;
                        }
                    }
                }
            }
            if (!isMove) return result;
            result++;
        }
    }

    public static int bfs(int x, int y) {
        Queue<Node> q = new LinkedList<>();
        list = new ArrayList<>();

        q.offer(new Node(x, y));
        list.add(new Node(x, y));
        visited[x][y] = true;

        int sum = board[x][y];
        while (!q.isEmpty()) {
            Node current = q.poll();

            for (int i = 0; i < 4; i++) {
                int nx = current.x + dx[i];
                int ny = current.y + dy[i];
                if (nx >= 0 && ny >= 0 && nx < n && ny < n && !visited[nx][ny]) {
                    int diff = Math.abs(board[current.x][current.y] - board[nx][ny]);
                    if (l <= diff && diff <= r) {
                        q.offer(new Node(nx, ny));
                        list.add(new Node(nx, ny));
                        sum += board[nx][ny];
                        visited[nx][ny] = true;
                    }
                }
            }
        }
        return sum;
    }

    public static void changePopulation(int sum) {
        int avg = sum / list.size();
        for (Node n : list) {
            board[n.x][n.y] = avg;
        }
    }

    public static class Node {
        int x;
        int y;

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