[백준 - G4] 16234. 인구 이동

문제 정리

map[r][c] 에는 각 나라면 인구 수가 들어있다.

인접한 두 나라의 인구 차가 L이상 R이하이면 연합을 만들고, 인구 이동을 시작한다.

인구 이동 후 연합 내 각 나라의 인구수는 (연합 인구 수) / 연합을 이루는 칸의 개수)

더 이상 인구 이동이 발생하지 않으면 종료한다. 인구 이동이 며칠 동안 발생하는 지 구하기

 

 

1. 아직 방문하지 않은 나라라면 방문(BFS)하고, 인구 수가 L이상 R이하인 인접 나라의 좌표를 union 리스트에 넣는다.

2. 리스트에 좌표가 2이상이면 인접한 나라가 1개 이상이므로, 인구 이동을 시작한다. 그리고 인구 이동 여부(moved)를 true로 변경한다.

3. 단, 각 연합은 하루에 한 번만 처리한다.

 

 

제출 코드

 

public class Solution {

    static int N, L, R;
    static int[][] map;
    static boolean[][] visited;

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] split = br.readLine().split(" ");
        N = Integer.parseInt(split[0]);
        L = Integer.parseInt(split[1]);
        R = Integer.parseInt(split[2]);

        map = new int[N][N];

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

        // 인구차이가 L이상, R이하
        // 연합의 인구수 / 연합을 이룬 칸의 수

        // 인접한 구역을 갈 수 있는 지 확인
        int ans = 0;
        while (true) {

            visited = new boolean[N][N];
            boolean moved = false;

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (!visited[i][j]) {
                        List<int[]> union = isOpen(i, j);

                        if (union.size() >= 2) {

                            moved = true;
                            int cnt = 0, population = 0;
                            cnt = union.size();
                            for (int[] curr : union) {
                                population += map[curr[0]][curr[1]];
                            }

                            for (int[] curr : union) {
                                map[curr[0]][curr[1]] = population / cnt;
                            }
                        }

                    }
                }
            }

            if (!moved) break;
            ans++;
        }

        System.out.println(ans);

    }

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

    static List<int[]> isOpen(int x, int y) {

        // visited[x][y] = true;
        List<int[]> tmp = new ArrayList<int[]>();
        Queue<int[]> queue = new ArrayDeque<int[]>();
        queue.offer(new int[] { x, y });
        tmp.add(new int[] { x, y });
        visited[x][y] = true;

        while (!queue.isEmpty()) {

            int[] curr = queue.poll();
            x = curr[0];
            y = curr[1];

            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if (nx < 0 || ny < 0 || nx >= N || ny >= N)
                    continue;

                int diff = Math.abs(map[x][y] - map[nx][ny]);
                if (!visited[nx][ny] && diff >= L && diff <= R) {
                    queue.offer(new int[] { nx, ny });
                    visited[nx][ny] = true;
                    tmp.add(new int[] { nx, ny });
                }
            }
        }

        return tmp;
    }

}

 

 

문제 링크

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