[Java] BOJ16234_인구 이동

www.acmicpc.net/problem/16234

16234번: 인구 이동

---

BFS를 돌아 두 나라의 인구 차이가 L 이상 R이하일 때 같은 tag을 부여하였다. tag값이 곧 연합을 의미한다.

 

tag를 부여할 때 tag의 수 tagCnt와 그 태그의 인구수 tagSum을 구하는데 BFS를 다 돌고 나서 tag 1(연합 1)의 tagCnt가 0이라면 어떠한 연합도 생기지 않은 것이므로 반복문을 빠져나온다.

 

그 경우가 아니라면 각 연합에 속해있는 나라들에 tagSum / tagCnt 값을 넣어준다.

 

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

public class Main {
	
	static int N, L, R;
	static boolean[][] visit;
	static int[][] arr;
	static int[][] tag;
	static int[] tagCnt;
	static int[] tagSum;
	static int[] dr = { -1, 0, 1, 0 };
	static int[] dc = { 0, -1, 0, 1 };
	public static void main(String[] args) throws IOException {
		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());
		
		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());
			}
		}
		int res = 0;
		while(true) {
			visit = new boolean[N][N];
			tag = new int[N][N];
			tagCnt = new int[(N*N)+1];
			tagSum = new int[(N*N)+1];
			int cnt = 1;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if(!visit[i][j]) {
						bfs(i, j, cnt);
						if(tagCnt[cnt] != 0) cnt++;
					}
				}
			}
			if(tagCnt[1] == 0) break;
			for (int c = 1; c < tagCnt.length; c++) {
				if(tagCnt[c] == 0) break;
				int cal = tagSum[c] / tagCnt[c];
				for (int i = 0; i < N; i++) {
					for (int j = 0; j < N; j++) {
						if(tag[i][j] == c) arr[i][j] = cal;
					}
				}
			}
			res++;
		}
		
		System.out.println(res);
		
	}
	private static void bfs(int r, int c, int tagNum) {
		Queue<int[]> q = new LinkedList<int[]>();
		q.offer(new int[] {r, c});
		visit[r][c] = true;
		
		while(!q.isEmpty()) {
			int[] temp = q.poll();
			
			for (int i = 0; i < 4; i++) {
				int nr = temp[0] + dr[i];
				int nc = temp[1] + dc[i];
				
				if(nr < 0 || nc < 0 || nr >= N || nc >= N || visit[nr][nc]) continue;
				
				int t = Math.abs(arr[temp[0]][temp[1]] - arr[nr][nc]);
				if(t >= L && t <= R) {
					q.offer(new int[] {nr, nc});
					tag[nr][nc] = tagNum;
					tagCnt[tagNum]++;
					tagSum[tagNum] += arr[nr][nc];
					visit[nr][nc] = true;
				}
			}
		}
		if(tagCnt[tagNum] != 0) {
			tag[r][c] = tagNum;
			tagCnt[tagNum]++;
			tagSum[tagNum] += arr[r][c];
		}
	}
}