16234번 - 인구 이동

1. 문제 정의

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번 보다 작거나 같은 입력만 주어진다.

- 출력 -

인구 이동이 며칠 동안 발생하는지 첫째 줄에 출력한다.

2. 문제 접근

처음에는 단순 bfs 문제였는지 알았는데 아니었다. bfs 에 응용이 필요했다.

 

3. 문제 풀이

while문을 돌면서 모든 칸을 순회하며 bfs 를 돌린다. 만약 인구이동이 되는 구역이면 list에 추가하여 인구 배분을 해준다. 인구 이동이 없을 경우, while문을 벗어난다.

 

4. 코드

import java.io.*;
import java.net.Inet4Address;
import java.util.*;

public class Main {
    static FastReader scan = new FastReader();
    static StringBuilder sb = new StringBuilder();

    static int N, L, R, result;
    static int[][] matrix;

    static ArrayList<int[]> list;

    static boolean[][] visited;

    static int[][] dir = {{1,0}, {0,1}, {-1,0}, {0,-1}};
    static void input(){
        N = scan.nextInt();
        L = scan.nextInt();
        R = scan.nextInt();

        matrix = new int[N][N];

        for(int i = 0; i < N; i++){
            String[] lines = scan.nextLine().split(" ");
           for(int j = 0; j < lines.length; j++){
               matrix[i][j] = Integer.parseInt(lines[j]);
           }
        }

        result = 0;
    }

    static void move(){

        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) break;
            result++;
        }
    }

    static void changePopulation(int sum){
        int avg =  sum/list.size();
        for (int[] ints : list) {
            int x = ints[0];
            int y = ints[1];
            matrix[x][y] = avg;
        }
    }


    static int bfs(int x, int y) {
        Queue<int[]> q = new LinkedList<>();
        list = new ArrayList<>();
        int sum = matrix[x][y];

        q.add(new int[]{x,y});
        visited[x][y] = true;

        list.add(new int[]{x,y});

        while(!q.isEmpty()){

            int[] t = q.poll();

            for(int d = 0; d < 4; d++){
                int nx = dir[d][0]+ t[0];
                int ny = dir[d][1]+ t[1];

                if(nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
                if(visited[nx][ny]) continue;
                int temp = Math.abs(matrix[t[0]][t[1]] - matrix[nx][ny]);
                if( L <= temp && temp <= R) {
                    visited[nx][ny] = true;
                    list.add(new int[]{nx, ny});
                    q.add(new int[]{nx,ny});
                    sum += matrix[nx][ny];
                }
            }

        }
        return sum;

    }

    public static void main(String[] args) {
        input();
        move();
        System.out.println(result);

    }


    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}

5. 회고

bfs 응용 1