Java 16234 인구이동

 

 

풀이 :
1. 모든 좌표에 대해 bfs로 탐색을 진행한다.

2. 상,하,좌,우로 인접한 나라(원소)와의 값의 차이가 L이상, R이하이면 인구 이동이 필요한 sumQ에 좌표값을 추가해준다.

3. bfs 탐색이 종료될 경우에 sumQ의 값이 1보다 크다면 인구이동이 필요한 경우이기 때문에 인구이동을 실행한다.

4. 모든 좌표에 대한 탐색이 종료된 경우 인구이동이 일어났다면 bool값을 true로 업데이트 해준 뒤 반복문을 계속 실행하며 day 값을 1 더해준다.

 

 

핵심 로직은 위와 같이 구현하였습니다.

 

 

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

public class Main {
    static int n, l, r;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int[][] map;
    static Queue<int[]> sumQ;
    static boolean[][] visited;

    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 day = 0;

        while (true) {
            boolean moved = 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 sum = bfs(i, j);
                        // sumQ의 사이즈가 1보다 커야지만 인구이동.
                        if (sumQ.size() > 1) {
                            sum /= sumQ.size();
                            while (!sumQ.isEmpty()) {
                                int[] poll = sumQ.poll();
                                map[poll[0]][poll[1]] = sum;
                            }
                            moved = true;
                        }

                    }
                }
            }
            if (!moved) {
                break;
            }
            day++;
        }

        System.out.println(day);
    }

    static int bfs(int x, int y) {
        Queue<int[]> q = new LinkedList<>();
        sumQ = new LinkedList<>();
        q.offer(new int[]{x, y});
        sumQ.offer(new int[]{x,y});
        visited[x][y] = true;
        int sum = map[x][y];

        while (!q.isEmpty()) {
            int[] poll = q.poll();

            x = poll[0];
            y = poll[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 || visited[nx][ny]) {
                    continue;
                }

                int val = Math.abs(map[x][y] - map[nx][ny]);
                if (val >= l && val <= r) {
                    sum += map[nx][ny];
                    q.offer(new int[]{nx, ny});
                    sumQ.offer(new int[]{nx, ny});
                    visited[nx][ny] = true;
                }
            }
        }

        return sum;
    }
}