[Algorithm] 백준/16234 :: 인구 이동

* 핵심

삼성기출중 쉬운편에 속하는 문제이다.

2중 For문을 돌면서 BFS로 탐색하면 된다.

문제에서 설명이 조금 애매한데, 몇 번이라기보다는 몇 일이 걸린다고 이해하는게 편하다.

하루에 인구 이동한 나라는 그 날은 또 다른 나라랑 연합을 맺을 수 없다.

문제에 주어진 마지막 예시를 보면,

1일차

2일차

3일차

위 예제를 보면 6번의 인구 이동이 있지만 3일에 걸쳐 인구 이동되었기 때문에 3을 출력하는 것이 맞다.

* 문제

문제

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]의 값이다. (1 ≤ A[r][c] ≤ 100)

인구 이동이 발생하는 횟수가 2,000번 보다 작거나 같은 입력만 주어진다.

출력

인구 이동이 몇 번 발생하는지 첫째 줄에 출력한다.

* 소스 코드

import java.io.*;
import java.util.*;
 
public class Main {
    public static StringTokenizer stk;
    public static StringBuilder sb = new StringBuilder();
    public static int[] dx = {1, -1, 0, 0};
    public static int[] dy = {0, 0, 1, -1};
    public static int min, max, ans = 0;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        stk = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(stk.nextToken());
        min = Integer.parseInt(stk.nextToken());
        max = Integer.parseInt(stk.nextToken());
        int[][] map = new int[n + 1][n + 1];
        boolean[][] visited = new boolean[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            stk = new StringTokenizer(br.readLine());
            for (int j = 1; j <= n; j++) {
                map[i][j] = Integer.parseInt(stk.nextToken());
            }
        }
        boolean hasMoreMoving = false;  //while문에서 인구이동 발생 여부 확인
        while (!hasMoreMoving) {
            Queue<Pair> q = new LinkedList<>();
            int sum = 0, cnt = 0;                           //sum = 인구 이동할 나라의 사람수, cnt = 인구 이동한 나라 개수
            ArrayList<Pair> alist = new ArrayList<>();      //해당 점을 방문했을 때 이동한 점의 좌표 정보
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    q.add(new Pair(i, j));
                    while (!q.isEmpty()) {
                        Pair p = q.poll();
                        if (!visited[p.x][p.y]) {
                            visited[p.x][p.y] = true;
                            cnt++;
                            sum += map[p.x][p.y];
                            alist.add(new Pair(p.x, p.y));
                            for (int k = 0; k < 4; k++) {
                                int nx = p.x + dx[k];
                                int ny = p.y + dy[k];
                                if (nx > 0 && nx <= n && ny > 0 && ny <= n && !visited[nx][ny] && checkPerson(map[p.x][p.y], map[nx][ny])) {
                                    q.add(new Pair(nx, ny));
                                }
                            }
                        }
                    }
 
                    //방문한 좌표가 인구 이동이 필요한 경우
                    if (alist.size() > 1) {
                        int movingSum = sum / cnt;
                        for (int k = 0; k < alist.size(); k++) {
                            Pair p = alist.get(k);
                            map[p.x][p.y] = movingSum;
                        }
                        hasMoreMoving = true;
                    }
                    //매 시작점마다 초기화
                    alist = new ArrayList<>();
                    sum = 0;
                    cnt = 0;
                }
            }   //end of for
            if (hasMoreMoving) {        //더이상 움직일 게 있다면 visited배열 초기화
                ans++;
                hasMoreMoving = false;
                visited = new boolean[n + 1][n + 1];
            } else break;
        }
        System.out.println(ans);
    }
 
    //현재 인구와 이동할 인구의 차이 계산
    public static boolean checkPerson(int curCnt, int nextCnt) {
        int absCnt = Math.abs(curCnt - nextCnt);
        if (absCnt >= min && absCnt <= max) return true;
        else return false;
    }
 
    public static class Pair {
        int x, y;
 
        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}