[ 백준 ] 16234 인구 이동

📌 Problem

N x N 크기의 땅에 각 칸 마다 나라가 세워져있다. 매일 인구 수의 차이에 따라 연합이 생성되고 연합끼리는 인구를 동일하게 이주시키며 하루가 끝나면 연합을 해체한다. 인구 이주가 몇일동안 발생하는지 구하면 되는 문제이다.

📌 Solution

어떤 나라끼리 연합을 구성하는지는 BFS를 통해서 구할 수 있다. 이때 이미 연합으로 구성된 나라를 재탐색하지 않게 주의한다. 만약 하루 동안 연합이 생성되지 않으면 더 이상의 연합 구성이 불가능하다고 판단한다.

예제 5번을 통해 solution을 작성하였다.

Initialize
예제 5번에서 N, L, R의 값은 각각 4, 10, 50이다. 각가의 나라에 대한 인구를 표현하면 다음과 같다.

Day 1
첫 번째 날에 대해 BFS를 수행하여 연합을 구성하면 다음과 같다.

연합의 총 인구수는 660이고 연합에 속한 나라의 수는 13개국이다. 이주를 하게 되면 연합의 모든 나라가 50명의 인구를 가지게 된다. 이주가 완료되고 연합을 해체한 상태는 다음과 같다.

Day 2
두 번째 날에 대해 BFS를 수행하여 연합을 구성하면 다음과 같다.

파랑, 노랑, 초록 연합의 총 인구수는 각각 60, 200, 250이며 연합에 속한 국가의 수는 각각 2, 3, 4개국이다. 이주를 하고 연합이 해체된 상태는 다음과 같다.

Day 3
세 번째 날에 대해 BFS를 수행하여 연합을 구성하면 다음과 같다.

파랑, 초록 연합에 대한 총 인구수는 각각 96, 648명이고 연합에 속한 국가의 수는 각각 2, 12개국이다. 이주를 하고 연합을 해체하면 다음과 같은 상태가 된다.

이후로는 인접 국가 간의 인구 수 차이가 10이상 50이하인 연합이 생성되지 않는다. 즉, 인구 이동은 3일동안만 진행된다.

📌 Code

// 도시의 위치, 인구, 연합 여부를 가진다.
static class Country {
    int row, col;
    int population;
    boolean unionized;

    public Country(int row, int col, int population) {
        this.row = row;
        this.col = col;
        this.population = population;
    }
}

// 이웃하는 도시는 현재 도시의 북, 동, 남, 서쪽에 위치한다.
final int[][] moves = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

int N, L, R;
Country[][] countries;

public void solve() throws IOException {
    init();
    result.append(migration());
}

/**
 * 전체 이주에 대한 함수이다.
 * @return 몇일 동안 이주가 이루어지는지 반환한다.
 */
private int migration() {
    int day = 0;
    while (searchCountries()) day++;
    return day;
}

/**
 * 하루에 대한 이주를 처리하는 함수이다.
 * 전체 나라들을 탐색하면서 연합을 확인한다.
 * @return 연합이 구성되어졌는지에 대한 여부
 */
private boolean searchCountries() {
    List<List<Country>> unions = new ArrayList<>(); // 각 연합의 국가 리스트에 대한 리스트
    for (int r = 1; r <= N; r++)
        for (int c = 1; c <= N; c++)
            if (!countries[r][c].unionized)         // 이미 연합이 이루어져 있으면 탐색을 하지 않는다.
                unions.add(new ArrayList<>(searchUnionsOf(countries[r][c])));   // 연합을 추가한다. (단일 국가 연합 가능)
    unions.forEach(union -> union.forEach(country -> country.unionized = false));   // 연합을 해체한다.
    return unions.size() != N * N;  // 연합의 수가 전체 국가의 수와 같다면 연합이 없는 것과 마찬가지이다.
}

/**
 * 특정 나라를 기준으로 연합을 이루는 나라들을 찾는다.
 * @param baseCountry 특정 나라
 * @return 연합을 이루는 도시 리스트
 */
private List<Country> searchUnionsOf(Country baseCountry) {
    baseCountry.unionized = true;
    int totalPopulation = baseCountry.population;

    List<Country> unions = new ArrayList<>(Collections.singleton(baseCountry));         // 연합국 리스트
    Queue<Country> neighbors = new LinkedList<>(Collections.singleton(baseCountry));    // BFS 자료구조
    while (!neighbors.isEmpty()) {
        Country country = neighbors.poll();
        for (int[] move : moves) {
            Country neighbor = countries[country.row + move[0]][country.col + move[1]];
            if (neighbor == null) continue;                                             // 대륙 크기 밖
            int sub = Math.abs(country.population - neighbor.population);               // 인구수 차이
            if (!neighbor.unionized && L <= sub && sub <= R) {
                totalPopulation += neighbor.population;
                neighbor.unionized = true;
                neighbors.offer(neighbor);
                unions.add(neighbor);
            }
        }
    }

    for (Country country : unions) country.population = totalPopulation / unions.size();    // 인구 이동
    return unions;
}

private void init() throws IOException {
    StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
    N = Integer.parseInt(tokenizer.nextToken());
    L = Integer.parseInt(tokenizer.nextToken());
    R = Integer.parseInt(tokenizer.nextToken());
    countries = new Country[N + 2][N + 2];
    for (int r = 1; r <= N; r++) {
        tokenizer = new StringTokenizer(reader.readLine());
        for (int c = 1; c <= N; c++) countries[r][c] = new Country(r, c, Integer.parseInt(tokenizer.nextToken()));
    }
}