[백준] 16234번 인구이동 - Java, 자바

16234번 인구이동

난이도

골드 5

문제 설명

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

문제

요구사항

• 크기 NxN격자, 각 칸은 나라의 인구 A[r][c].
• 1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100, 0 ≤ A[r][c] ≤ 100, 인구 이동 일수는 ≤ 2000 보장
• 하루동안 인구 이동이 없으면 종료.
• 인접한 칸의 인구 차이가 L 이상, R 이하이면 국경 개방 및 연합
• 연합된 모든 나라의 인구를 '연합 총 인구 / 연합 수'(소수점은 제외)로 재분배.
• 연합 해제 및 국경 닫기.

접근 방식

핵심은 BFS를 사용하여 그날의 연합들을 찾아 연합 단위로 일괄 처리하는 것 이다.

하루가 시작될 때마다 visited 방문 배열을 초기화하여 날마다 각 칸의 방문 여부를 확인하였다. 이후 모든 칸에 대해 BFS를 돌며, 조건(인접한 칸과의 인구 차 L <= diff <= R)에 만족하면 같은 연합으로 묶고 list 자료에 저장하였다. 그 후, 해당 연합의 인구 수 / 연합의 나라의 수를 구하여 해당 연합의 인구를 초기화하였다.

만약, list의 크기가 1이하이면 연합이 생성되지 않은 것이기 때문에 해당 상황은 건너뛴다. list의 크기가 1보다 크다면, 연합이 생성되어 인구 이동이 발생한 것이기 때문에 move = true로 초기화하여 다음 날로 넘어가 위의 작업을 인구 이동이 발생하지 않을 때까지 반복하여 문제를 해결하였다.

이 문제는 연합 탐색 중에는 값을 변경하지 않아야 하고 연합을 다 모은 후 일괄 갱신해야하는 것이 중요하였다.

코드

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

class Point{
    int x;
    int y;

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

public class Main{
    static int n, l, r, answer = 0;
    static int[][] arr;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, -1, 0, 1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        l = Integer.parseInt(st.nextToken());
        r = Integer.parseInt(st.nextToken());
        arr = new int[n][n];
        for(int i=0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<n; j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        while (true){
            boolean[][] visited = new boolean[n][n];
            boolean move = false;
            for(int i=0; i<n; i++){
                for(int j=0; j<n; j++){
                    if(visited[i][j]) continue;

                    visited[i][j] = true;
                    ArrayList<Point> al = new ArrayList<>();
                    Queue<Point> q = new LinkedList<>();

                    al.add(new Point(i, j));
                    q.offer(new Point(i, j));
                    while (!q.isEmpty()){
                        Point now = q.poll();
                        for(int d=0; d<4; d++){
                            int nx = now.x + dx[d];
                            int ny = now.y + dy[d];

                            if(nx<0 || nx>=n || ny<0 || ny>=n) continue;
                            if(visited[nx][ny]) continue;
                            int diff = Math.abs(arr[now.x][now.y] - arr[nx][ny]);
                            if(diff < l || diff > r) continue;

                            visited[nx][ny] = true;
                            al.add(new Point(nx, ny));
                            q.offer(new Point(nx, ny));
                        }
                    }

                    if(al.size()>1){
                        int sum = 0;
                        for(Point p : al){
                            sum += arr[p.x][p.y];
                        }

                        int result = sum / al.size();
                        for(Point p : al){
                            arr[p.x][p.y] = result;
                        }
                        move = true;
                    }
                }
            }
            if(!move){
                System.out.println(answer);
                break;
            }
            answer++;
        }
    }
}

느낀점

하루 반복과 연합 탐색을 구현하기 위한 시뮬레이션 루프 설계가 초반엔 어렵게 느껴졌다. 그러나 조건을 작은 단계로 분해해 순서대로 구현하니 금방 풀렸다. 이번 문제로, 시뮬레이션은 모든 규칙을 한꺼번에 처리하려 하기보다 규칙을 정리->탐색->일괄 갱신의 흐름으로 쪼개 구현하는 게 핵심임을 다시 확인했다.