[백준_16234] 인구 이동

문제

백준 16234번
https://www.acmicpc.net/problem/16234

N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다.

오늘부터 인구 이동이 시작되는 날이다.

인구 이동은 하루 동안 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.

• 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루 동안 연다.
• 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.
• 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.
• 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.
• 연합을 해체하고, 모든 국경선을 닫는다.

각 나라의 인구수가 주어졌을 때, 인구 이동이 며칠 동안 발생하는지 구하는 프로그램을 작성하시오.

첫째 줄에 N, L, R이 주어진다. (1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100)
둘째 줄부터 N개의 줄에 각 나라의 인구수가 주어진다. r행 c열에 주어지는 정수는 A[r][c]의 값이다. (0 ≤ A[r][c] ≤ 100)

인구 이동이 발생하는 일수가 2,000번 보다 작거나 같은 입력만 주어진다.
인구 이동이 며칠 동안 발생하는지 첫째 줄에 출력한다.

• 생각해보기

Code

• 이동할 move 메서드를 만든다.
• 방문 확인을 위해 isVisited를 만들고 방문을 했다면 continue해준다.
• 방문을 하지 않았다면 현재 나라에서 bfs를 통해 주변 나라의 인구를 한다.
• bfs에 queue를 통해 현재 나라의 좌표를 넣고 상, 하, 좌, 우의 나라를 확인한다.
• 그 중 범위를 벗어난 위치에 대해서는 continue를 통해 넘어간다.
• 범위 안에 있는 나라에 대해서는 L(최소)< 인구 수의 차이 < R(최대) 를 통해 이동한 나라에 대해 queue에 넣어주고 isVisited에 방문 확인으로 true를 만들어준다.
• 또한, 이동할 인구에 대해서 sum을 하고 list를 통해 인구가 이동해야 할 나라에 대해 넣어준다.
• 상, 하, 좌, 우 다 끝나면 bfs를 종료하고 이동할 나라에 대해 인구 수의 합(sum)과 list(인구가 이동해야 할 나라들의 좌표)의 size를 통해 평균을 구한다.
• 이동해야할 나라에 대해서는 평균값으로 대체한다.
• 그리고 isMove를 통해 이동했음을 표시한다.
• 위 순서를 반복하면서 더 이상 인구 수의 차이가 최소인 L과 최대인 R 사이의 존재하지 않는다면 총 이동한 횟수에 대해 반환한다.

Java

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

class Node {
    int x;
    int y;

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

public class Main {
    static int N, L, R;
    static int[][] board;
    static boolean[][] isVisited; // 방문 확인
    static int[] dx = {0, 1, 0, -1}; // x축 이동
    static int[] dy = {1, 0, -1, 0}; // y축 이동
    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;
            isVisited = new boolean[N][N];

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (isVisited[i][j]) { // 이전의 방문 했을 경우
                        continue;
                    }
                    // 현재 나라에서 주변 나라를 확인하며 이동할 인구 수의 총합 
                    int sum = bfs(i, j);

                    if (list.size() > 1) {
                        // 인구 변경
                        int avg = sum / list.size();
                        for (Node node : list) {
                            board[node.x][node.y] = avg;
                        }
                        isMove = true;
                    }
                }
            }

            if (!isMove) { // 더 이상 이동이 없을 경우
                return result;
            }
            result++;
        }
    }

    public static int bfs(int i, int j) {
        Queue<Node> queue = new LinkedList<>();
        list = new ArrayList<>();

        queue.offer(new Node(i, j));
        list.add(new Node(i, j));
        isVisited[i][j] = true;

        int sum = board[i][j];
        while (!queue.isEmpty()) {
            Node cur = queue.poll();

            for (int k = 0; k < dx.length; k++) {
                // 주변 나라로 이동
                int x = cur.x + dx[k];
                int y = cur.y + dy[k];

                // 범위에서 벗어났을 경우
                if (x < 0 || y < 0 || x >= N || y >= N || isVisited[x][y]) {
                    continue;
                }
                // 주변 나라와의 인구 수의 차이
                int diff = Math.abs(board[cur.x][cur.y] - board[x][y]);
                // 지정한 최소 및 최대 인구 수 사이에 있는 경우
                if (L <= diff && diff <= R) {
                    queue.offer(new Node(x, y));
                    list.add(new Node(x, y));
                    sum += board[x][y];
                    isVisited[x][y] = true;
                }
            }
        }
        return sum;
    }
}