[백준] 16234 - 인구 이동

[문제링크]

16234번: 인구 이동

 

0. 국경선을 여는, 연합을 구한 다음, 연합 국가들의 인구를 공통 배분한다

  - 더이상 연합이 형성되지 않을때까지 반복

 

1. L 이상 R 이하일때 진행하는 DFS로 연합과 그 인구를 구한다

  - 인구는 DFS 결과로 반환, 연합은 tempMap 배열에 idx를 작성한다

 

2. 연합이 형성되지 않았다면, 즉 DFS가 호출된 횟수가 국가의 횟수와 같다면 종료 후 소요된 day 출력

 

3. 연합이 형성되었다면, 인구수를 골고루 분배해 갱신한다 (소숫점은 버리므로 int 간 나눗셈)

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		 n = pint(st.nextToken());
		L = pint(st.nextToken());
		R = pint(st.nextToken());
		map = new int[n][n];
		
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < n; j++) {
				map[i][j]=pint(st.nextToken());
			}
		}
		
		int day=0;
		while(true) {
			union = new ArrayList<>();
			tempMap=new int[n][n];
			
			int cnt=1;
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					if(tempMap[i][j]==0) {
						//union을 찾아서,
						//전체 합계와 나라 갯수를 저장한다
						num=0;
						union.add(new int[] {find(i,j,cnt++), num});
					}
				}
			}
			
			if(cnt==n*n+1)break;//union이 없으면 끝, 탈출한다
			
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					//찾은 union정보를 바탕으로 각 나라별 새 인구를 채워넣는다
					map[i][j]=union.get(tempMap[i][j]-1)[0] / union.get(tempMap[i][j]-1)[1];
				}
			}
			day++;
			
		}
		System.out.println(day);
		
	}
	static int n,L,R, num;
	static ArrayList<int[]> union;
	static int[][]map;
	static int[][]tempMap;
	
	static int find(int x, int y, int cnt) {
		tempMap[x][y]=cnt;
		num++;
		int popul=map[x][y];
		if(x>0 && tempMap[x-1][y]==0
				&& Math.abs(map[x-1][y]-map[x][y])>=L
				&& Math.abs(map[x-1][y]-map[x][y])<=R) {
			popul+=find(x-1,y,cnt);
		}
		if(x<n-1 && tempMap[x+1][y]==0
				&& Math.abs(map[x+1][y]-map[x][y])>=L
				&& Math.abs(map[x+1][y]-map[x][y])<=R) {
			popul+=find(x+1,y,cnt);
		}
		if(y>0 && tempMap[x][y-1]==0
				&& Math.abs(map[x][y-1]-map[x][y])>=L
				&& Math.abs(map[x][y-1]-map[x][y])<=R) {
			popul+=find(x,y-1,cnt);
		}
		if(y<n-1 && tempMap[x][y+1]==0
				&& Math.abs(map[x][y+1]-map[x][y])>=L
				&& Math.abs(map[x][y+1]-map[x][y])<=R) {
			popul+=find(x,y+1,cnt);
		}
		
		return popul;
		
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
	
}

결과 화면