백준 16234 - 인구 이동

문제

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

풀이

인구 이동은 BFS를 통해 구현하였다.

• 매턴마다 방문 배열을 초기화하여 사용한다.
• 모든 방문하지 않은 좌표(나라)에 대해 BFS를 수행하며 인접한 좌표중 인구 수 차이 조건을 충족하는 좌표를 모두 List에 모은다.
• 모은 좌표 정보를 바탕으로 해당 나라간 인구 수 조정 작업을 수행한다.

한편, 인구 이동 가능 여부를 확인하기 위해 각 턴에서 모은 좌표 개수중 최대값(count)을
구한다. 이 최대값이 1 이하일 경우 진입 좌표를 제외한 나머지 좌표로 BFS 수행 시 이동하지
않았다는 얘기이므로, 더 이상 인구 이동될 수 없다는 의미이다. 이 값을 통해 종료 여부를
판단한다.

while문내에서 각 좌표에 대해 BFS를 수행하는 부분이 $O(N^4)$의 시간복잡도로
수렴한다. 하지만 $N=50$이 최악의 경우이므로, 무난히 주어진 제한 조건 2초를 통과한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

import static java.lang.Integer.parseInt;

public class Main {
    static int[][] matrix;

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

        matrix = new int[N][N];
        for (int r = 0; r < N; r++) {
            st = new StringTokenizer(br.readLine());
            for (int c = 0; c < N; c++) {
                matrix[r][c] = parseInt(st.nextToken());
            }
        }

        int day = 0;

        while (true) {
            boolean[][] visited = new boolean[N][N];
            int count = 0;

            for (int r = 0; r < N; r++) {
                for (int c = 0; c < N; c++) {
                    if (visited[r][c]) continue;

                    List<Node> nodes = collectNodes(N, L, R, r, c, visited);
                    if (nodes.isEmpty()) continue;

                    count = Math.max(count, nodes.size());
                    movePeople(nodes);
                }
            }

            if (count <= 1) break;
            day++;
        }

        System.out.println(day);
        br.close();
    }

    static List<Node> collectNodes(int N, int L, int R, int r, int c, boolean[][] visited) {
        visited[r][c] = true;

        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(r, c));

        int[] dr = {1, -1, 0, 0};
        int[] dc = {0, 0, -1, 1};
        List<Node> nodes = new ArrayList<>();

        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            nodes.add(cur);

            for (int i = 0; i < dr.length; i++) {
                int nr = cur.r + dr[i];
                int nc = cur.c + dc[i];

                if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue;

                if (visited[nr][nc]) continue;

                int diff = Math.abs(matrix[cur.r][cur.c] - matrix[nr][nc]);
                if (diff < L || diff > R) continue;

                visited[nr][nc] = true;
                queue.add(new Node(nr, nc));
            }
        }

        return nodes;
    }

    static void movePeople(List<Node> nodes) {
        int sum = nodes.stream().mapToInt(node -> matrix[node.r][node.c]).sum();
        int value = sum / nodes.size();

        for (Node node : nodes) {
            matrix[node.r][node.c] = value;
        }
    }

    static class Node {
        int r, c;

        public Node(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
}

결과