16234. 인구 이동

문제 개요

인구 이동이 한번 발생하는 과정을 사이클이라고 할 때, 총 몇번의 사이클이 발생하는지 구하는 문제입니다.

문제 접근

인구 이동이 발생하는 연합은 BFS나 DFS를 이용해 찾을 수 있습니다. 그리고 Java의 stream을 이용하면 손쉽게 평균을 구할 수 있습니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Queue;
import java.util.Set;
import java.util.stream.Collectors;

class Pos{
    private int row;
    private int col;

    public Pos(int row, int col){
        this.row = row;
        this.col = col;
    }

    public int getRow() {
        return row;
    }
    public void setRow(int row) {
        this.row = row;
    }
    public int getCol() {
        return col;
    }
    public void setCol(int col) {
        this.col = col;
    }
}

public class Main {
    static int N;
    static int L;
    static int R;

    static int[][] countries;

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

    public static void input() throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] firstLine = bf.readLine().split(" ");
        N = Integer.parseInt(firstLine[0]);
        L = Integer.parseInt(firstLine[1]);
        R = Integer.parseInt(firstLine[2]);
        countries = new int[N][];
        for(int i=0;i<N;i++){
            countries[i] = Arrays.stream(bf.readLine().split(" "))
                                 .mapToInt(Integer::parseInt).toArray();
        }
    }

    static Set<Pos> bfs(Pos cur, boolean[][] isChecked){
        Queue<Pos> q = new ArrayDeque<>();
        Set<Pos> unite = new HashSet<>();
        q.add(cur);
        unite.add(cur);
        isChecked[cur.getRow()][cur.getCol()] = true;
        while(!q.isEmpty()){
            cur = q.remove();
            for(int i=0;i<4;i++){
                Pos next = new Pos(cur.getRow()+dirs[i][0], cur.getCol()+dirs[i][1]);
                if(next.getRow() < 0 || next.getCol() < 0 || next.getRow() >= N || next.getCol() >= N){
                    continue;
                }
                if(isChecked[next.getRow()][next.getCol()]){
                    continue;
                }
                int differ = Math.abs(countries[next.getRow()][next.getCol()] - countries[cur.getRow()][cur.getCol()]);
                if(differ > R || differ < L){
                    continue;
                }
                q.add(next);
                unite.add(next);
                isChecked[next.getRow()][next.getCol()] = true;
            }
        }
        return unite;
    }

    static List<Set<Pos>> getUniteds(){
        boolean[][] isChecked = new boolean[N][N];
        List<Set<Pos>> unitedes = new ArrayList<>();
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(isChecked[i][j]){
                    continue;
                }
                unitedes.add(bfs(new Pos(i, j), isChecked));
            }
        }
        return unitedes;
    }

    static boolean moving(List<Set<Pos>> unitedes){
        boolean isMoved = false;
        for(var unite : unitedes){
            if(unite.size() == 1){
                continue;
            }
            int average = unite.stream().collect(Collectors.averagingInt(pos -> countries[pos.getRow()][pos.getCol()])).intValue();
            unite.stream().forEach(pos -> countries[pos.getRow()][pos.getCol()] = average);
            isMoved = true;
        }
        return isMoved;
    }

    public static void process() {
        int days = 0;
        while(moving(getUniteds())){
            days++;
        }
        System.out.println(days);
    }

    public static void main(String[] args) throws IOException {
        input();
        process();
    }
}

문제

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