BOJ (Java) 16234번: 인구 이동

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

---

풀이

bfs로 탐색하며 인구 수의 차이가 주어진 조건 내에 들어가는 나라들끼리 묶은 후, 인구 수를 재배치했다.

 

각 나라가 어떤 연합인지 저장하는 배열(union)과, 각 연합이 생겼을 때 나라 별 인구 수 (총 인구 수 / 연합 나라 수)를 저장할 맵(map) 하나를 만든다.

bfs로 탐색하며 각 나라 별로 연합을 결정(groupNum)하여 배열(union)에 저장한 후, 연합의 총 인구 수(sum)와 나라 수(cnt)를 구했다.

이를 토대로 연합 별 인구 수(sum / cnt)를 구한 후 맵(groupNum, sum/cnt) 에 저장하였고, 인구를 이동(movePeople)시켰다.

이 때 인구 수가 변경되는 나라가 하나도 없다면(isMoved) 탐색을 종료한 후, 이동에 걸린 총 일자를 반환한다.

---

Java 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Queue;

public class Main {
    private static int N, L, R;
    private static int[][] A, union;
    private static Map<Integer, Integer> map = new HashMap<>();
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        String[] inputs = bf.readLine().split(" ");
        N = Integer.parseInt(inputs[0]);
        L = Integer.parseInt(inputs[1]);
        R = Integer.parseInt(inputs[2]);

        A = new int[N][N];
        union = new int[N][N];

        for (int i = 0; i < N; i++) {
            inputs = bf.readLine().split(" ");
            for (int j = 0; j < N; j++) {
                A[i][j] = Integer.parseInt(inputs[j]);
            }
        }

        int cnt = 0;
        while (true) {
            // init
            for (int i = 0; i < N; i++) {
                Arrays.fill(union[i], 0);
            }
            map.clear();
            
            makeUnion();
            
            // 어떤 인구이동도 일어나지 않았다면 종료
            if (!movePeople()) break;
            cnt++;
        }
        System.out.println(cnt);
    }

    private static void makeUnion() {
        // 각 연합을 만듦
        int groupNum = 1;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (union[i][j] == 0) {
                    bfs(i, j, groupNum);
                    groupNum++;
                }
            }
        }
    }

    private static void bfs(int r, int c, int groupNum) {
        int[][] mv = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

        Queue<Cor> q = new ArrayDeque<>();
        q.add(new Cor(r, c));
        union[r][c] = groupNum;

        int sum = A[r][c];
        int cnt = 1;

        while (!q.isEmpty()) {
            Cor now = q.poll();

            for (int i = 0; i < 4; i++) {
                int nr = now.r + mv[i][0];
                int nc = now.c + mv[i][1];

                if (nr < 0 || nc < 0 || N <= nr || N <= nc || union[nr][nc] != 0) continue;

                // L <= 인구 수 차이 <= R 라면 같은 그룹으로 묶음
                int diff = Math.abs(A[now.r][now.c] - A[nr][nc]);
                if (L <= diff && diff <= R) {
                    q.add(new Cor(nr, nc));
                    union[nr][nc] = groupNum;
                    sum += A[nr][nc];
                    cnt++;
                }
            }
        }

        // 현재 연합의 조정된 인구 수를 map에 저장
        map.put(groupNum, sum / cnt);
    }

    static class Cor {
        int r;
        int c;

        public Cor(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
    
    private static boolean movePeople() {
        boolean isMoved = false;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                
                // 현재 연합에 저장된 인구 수로 변경
                int people = map.get(union[i][j]);
                
                // 인구 이동이 일어나는지 확인
                if (A[i][j] != people) isMoved = true;
                A[i][j] = people;
            }
        }
        return isMoved;
    }

}