[백준 16234] 인구 이동 (JAVA)

문제 링크: https://www.acmicpc.net/problem/16234

16234번: 인구 이동

1. 주의할 점

- 언제 While문을 끝내야 하는지 알아야 한다

- 연합되는 국가를 어떻게 확인할지 알아야 한다

 

2. 구현

- Check[][]를 통해 연합국가의 번호를 체크한다

- Arr[][]를 통해 각 독립국가의 인구수를 저장한다

- Tot[]를 통해 해당 연합국가에 포함된 인구의 총합를 저장한다

- Number[]를 통해 해당 국가에 속한 독립국가의 수를 저장한다

- While문을 진행하며, 끝나는 조건으로는 Arr[][]배열의 원소가 1개라도 바뀌지 않았을 경우

- BFS를 통해 연합국가를 묶으면서 Tot, Number배열을 갱신한다

- 연합국가의 인구수/연합국가에 포함된 국가의 수를 Arr[][]배열에 저장하는데, 변동이 1개라도 있는 경우 Change값을 True로 바꿔서 While문을 계속 실행하며, 만약 변동이 1개도 없다면 While문을 종료한다

 

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

public class Main_bj_16234_인구이동 {
	static int arr[][],check[][];		//사람수, 연합 국가
	static int num,l,r;
	final static int dx[]= {0,1,0,-1};
	final static int dy[]= {-1,0,1,0};
	static class Info{
		int x,y;
		public Info(int y, int x) {
			this.x=x;
			this.y=y;
		}
	}
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String s = br.readLine();
		StringTokenizer st = new StringTokenizer(s);
		num = Integer.parseInt(st.nextToken());
		l = Integer.parseInt(st.nextToken());
		r = Integer.parseInt(st.nextToken());
		arr = new int[num][num];
		
		for(int i=0;i<num;i++) {
			String str = br.readLine();
			StringTokenizer st2 = new StringTokenizer(str);
			for(int j=0;j<num;j++) 
				arr[i][j]=Integer.parseInt(st2.nextToken());
		}
		int result=0;
		Info ii;
		while(true) {
			int cnt=0;
			check = new int[num][num];
			int tot[] = new int[2501];			//해당 국가에 포함된 인구의 합
			int number[] = new int[2501];		//해당 국가에 속한 칸의 수
			for(int i=0;i<num;i++) {
				for(int j=0;j<num;j++) {
					if(check[i][j]==0) {
						cnt++;
						check[i][j]=cnt;						
						Queue<Info> q = new LinkedList<>();
						q.offer(new Info(i,j));
						while(!q.isEmpty()) {
							ii = q.poll();
							int cx = ii.x;
							int cy = ii.y;
							tot[cnt]+=arr[cy][cx];
							number[cnt]++;
							for(int k=0;k<4;k++) {
								int nx = cx + dx[k];
								int ny = cy + dy[k];
								if(nx>=0 && ny>=0 && nx<num && ny<num && check[ny][nx]==0 && l<=Math.abs(arr[ny][nx]-arr[cy][cx]) && Math.abs(arr[ny][nx]-arr[cy][cx])<=r ) {
									check[ny][nx]=cnt;
									q.offer(new Info(ny,nx));
								}
							}
						}
					}
				}
			}
			boolean change = false;
			for(int i=0;i<num;i++) {
				for(int j=0;j<num;j++) {
					int country = check[i][j];
					int vv = tot[country]/number[country];
					if(arr[i][j]!=vv) {
						change=true;
						arr[i][j]=vv;
					}
				}
			}
			if(!change) break;
			result++;
		}
		System.out.println(result);
	}
}