백준 16234 - 인구 이동

문제

16234번: 인구 이동

---

조건

• L ≤ 국경선을 공유하는 두 나라의 인구 차이 ≤ R → 하루 동안 국경선 열기
• 열어야하는 국경선이 모두 열렸다면, 인구 이동 시작
• 연합을 이룰 때 각 칸의 인구수 = (연합의 인구수) / (연합을 이루고 있는 칸의 개수) , 이때 소수점은 버린다.
• 인구 이동이 며칠 동안 발생하는지 구해야 함.

---

접근법

1. 배열의 모든 인덱스를 순회
2. 방문하지 않은 인덱스에 대해 bfs 탐색
3. bfs를 종료하고 탐색하면서 얻은 방문한 배열의 값과 개수를 이용해서 인구 이동 구현
4. 인구 이동이 끝났으면 그 다음 인덱스부터 다시 순회, 방문하지 않은 인덱스에 대해 2~3 과정 반복
5. 모든 인덱스를 방문했으면 다시 처음 인덱스로 돌아간다.
6. 1~5의 과정을 반복하면서 모든 인덱스에 대해 인구 이동이 없으면 종료
7. 인구 이동이 며칠 동안 발생한지 리턴

---

구현

• 구현 문제는 코드가 길어지므로 기능들에 대한 세분화 작업을 해야 가독성이 좋다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class p16234 {

    private static int N, L, R;
    private static int[][] map;
    private static boolean[][] visited;
    private static int[] dx = {-1, 1, 0, 0};
    private static int[] dy = {0, 0, -1, 1};
    private static ArrayList<Node> list; //인구이동이 될 Node를 담을 list

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());

        map = new int[N][N];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int moveDays = 0;

        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 avg = bfs(i, j);
                        if (list.size() > 1) {
                            movePopulation(avg);
                            isMove = true;
                        }
                    }
                }
            }
            if (!isMove) break;

			//모든 인덱스를 탐색하면 인구 이동에 대한 모든 처리가 끝났으므로 하루가 지난다.
            moveDays++;
        }

        System.out.println(moveDays);
    }

    public static int bfs(int x, int y) {
        Queue<Node> queue = new LinkedList<>();
        list = new ArrayList<>();

        int sum = map[x][y];

        queue.add(new Node(x, y));
        list.add(new Node(x, y));
        visited[x][y] = true;

        while (!queue.isEmpty()) {
            Node now = queue.poll();
            for (int k = 0; k < 4; k++) {
                int next_x = now.x + dx[k];
                int next_y = now.y + dy[k];
                if (next_x >= 0 && next_y >= 0 && next_x < N && next_y < N && !visited[next_x][next_y]) {
                    int diff = Math.abs(map[now.x][now.y] - map[next_x][next_y]);
                    if (diff >= L && diff <= R) {
                        queue.add(new Node(next_x, next_y));
                        visited[next_x][next_y] = true;
                        sum += map[next_x][next_y];
                        list.add(new Node(next_x, next_y));
                    }
                }
            }
        }

        return sum/list.size();
    }

    public static void movePopulation(int avg) {
        for (Node node : list) {
            map[node.x][node.y] = avg;
        }
    }

    public static class Node{
        int x;
        int y;

        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}