[Algorithm] 인구 이동

문제

N X N 크기의 땅이 있고, 땅은 1 X 1개의 칸으로 나누어져 있다.

각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다.

인접한 나라 사이에는 국경선이 존재한다.

오늘부터 인구 이동이 시작되는 날이다. 인구 이동은 아래와 같이 진행되고, 더 이상 인구 이동이 없을 때까지 지속된다.

 

1. 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면 두 나라가 공유하는 국경선은 오늘 하루 동안 연다.

2. 위의 조건에 의해 열어야 하는 국경선이 모두 열렸다면 인구 이동을 시작한다.

3. 국경선이 열려 있어 인접한 칸만을 이용해 이동할 수 있으면 그 나라를 오늘 하루 동안 연합이라고 한다.

4. 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루는 칸의 개수) 가 된다.

5. 연합을 해체하고 모든 국경선을 닫는다.

 

각 나라의 인구가 주어졌을 때, 인구 이동이 몇번 일어나는지?

 

풀이

1. 인구 차이가 L명 이상, R명 이하라는 조건에 따라 연합이 형성된다. (연합을 나누는 것이 필요함.)

 BFS를 활용한다. 큐에 연합을 이룰 수 있는 국가를 넣어서 조건에 따라 연합을 이루도록 한다. 

2. 연합이 완성된 후에 연합에 대해 인구 분배

 연합을 이루는 국가의 인구 총합을 계산하고, 분배한다.

 

전체 소스코드

import java.util.*;

class Position {
    private int x;
    private int y;
    public Position (int x, int y) {
        this.x = x;
        this.y = y;
    }
    public int getX() {return this.x;}
    public int getY() {return this.y;}
}

public class Main {

    public static int n, l, r;
    public static int[][] graph = new int[51][51];

    public static int[][] union = new int[51][51];

    public static int[] dx = {1, 0, -1, 0};
    public static int[] dy = {0, 1, 0, -1};

    public static void united(int x, int y, int index) {
        // 연합에 속하는 나라 리스트
        ArrayList<Position> list = new ArrayList<>();
        list.add(new Position(x, y));

        // 주변국에 연합할 수 있는 나라 확인하며 탐색
        Queue<Position> q = new LinkedList<>();
        q.offer(new Position(x, y));
        union[x][y] = index;

        int sum = graph[x][y];
        int cnt = 1;
        while (!q.isEmpty()) {
            Position now = q.poll();
            x = now.getX();
            y = now.getY();
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (0 <= nx && nx < n && 0 <= ny && ny < n && union[nx][ny] == -1) {
                    int diff = Math.abs(graph[x][y] - graph[nx][ny]);
                    if (l <= diff && diff <= r) {
                        union[nx][ny] = index;
                        sum += graph[nx][ny];
                        cnt++;
                        q.offer(new Position(nx, ny));
                        list.add(new Position(nx, ny));
                    }
                }
            }
        }
        // 연합된 나라 인구 분배
        for (int i = 0; i < list.size(); i++) {
            x = list.get(i).getX();
            y = list.get(i).getY();
            graph[x][y] = sum / cnt;
        }

    }

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        l = sc.nextInt();
        r = sc.nextInt();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                graph[i][j] = sc.nextInt();
            }
        }
        int cnt = 0;
        while (true) {
            // 연합 초기화
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    union[i][j] = -1;
                }
            }
            // 연합 지정
            int index = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (union[i][j] == -1) {
                        united(i, j, index);
                        index++;
                    }
                }
            }
            // 모든 나라가 연합을 이루지 않을 때
            if (index == n * n) break;
            cnt++;
        }
        System.out.println(cnt);
    }
        
}