[BOJ] 16234 인구 이동

 

 

[문제]

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

 

 

[소스 코드]

import java.io.*;
import java.util.*;

public class Main {
	static int[] dr = {-1,1,0,0};
	static int[] dc = {0,0,-1,1};
	static int n,l,r;
	static int[][] A;
	static boolean check;
	static boolean[][] visit;
	public static void main(String[] args) throws Exception {
		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());
		A = new int[n][n];
		for(int i=0;i<n;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<n;j++) {
				A[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		int result = 0;
		while(true) {
			check = false;
			visit = new boolean[n][n];
			for(int i=0;i<n;i++) {
				for(int j=0;j<n;j++) {
					if(!visit[i][j]) {
						bfs(i,j);
					}
				}
			}
			if(!check) break;
			result++;
		}
		System.out.println(result);
	}
	private static void bfs(int i,int j) {
		List<int[]> list = new ArrayList<>();
		list.add(new int[] {i,j});
		int sum = A[i][j];
		Queue<int[]> q = new LinkedList<>();
		q.offer(new int[] {i,j});
		visit[i][j] = true;
		while(!q.isEmpty()) {
			int[] curr = q.poll();
			for(int d=0;d<4;d++) {
				int nr = curr[0] + dr[d];
				int nc = curr[1] + dc[d];
				if(nr<0 || nr>=n || nc<0 || nc>=n || visit[nr][nc]) continue;
				int diff = Math.abs(A[curr[0]][curr[1]] - A[nr][nc]);
				if(diff>=l && diff<=r) {
					q.offer(new int[] {nr,nc});
					visit[nr][nc] = true;
					sum += A[nr][nc];
					list.add(new int[] {nr,nc});
				}
			}
		}
		if(list.size()>1) {
			check = true;
			sum /= list.size();
			for(int[] v : list) {
				A[v[0]][v[1]] = sum;
			}
		}
		else {
			visit[i][j] = false;
		}
	}
}