[BOJ 16234/Java]인구 이동

문제 요약

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

16234번: 인구 이동

문제를 봤을 때 어... 시뮬레이션인가..? 그냥 다 해보면 되는건가..? 했는데

입출력 봤을 때 나라 크기가 50*50이 최대길래 시뮬레이션 맞네 하고 풀었다.

이 문제에서 포인트는 연합이 될 국가를 찾아서 인구수 업데이트를 효율적으로 하는 것이라고 생각했다.

연합이 확정되면 연합에 포함되는 인구수도 확정되는데, 이를 연합을 찾으면서 한번에 계산할 수 있으면 속도가 더 빠를것이라고 생각했다.

 

그래서 문제에서 구현한 것은

1. 시뮬레이션 함수

   - 각 칸에 대하여 연합에 포함되어 있지 않다면 bfs 함수를 호출하여 연합을 찾음

   - 총 연합의 수를 체크하고, 각 연합 별 인구 수를 따로 저장해둔다.

   - 인구 수를 업데이트한다. (연합이 국가 수 만큼 생겼다면 시뮬레이션을 종료한다)

  

2. bfs

    - bfs 탐색을 통해서 연합을 찾고 그와 동시에 연합에 포함된 국가 수, 인원 수를 계산한다.

    - 마지막 return 값으로 (연합 인원수)/(국가 수)를 return 한다.

구현 코드

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

public class Main {

	static int N, L, R;
	static int[][] A;
	static int[][] united;
	
	static int[][] direction = {
			{0, 1}, {1, 0}, {-1, 0}, {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());
		
		A = new int[N][N];
		united = 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());
				united[i][j] = -1;
			}
		}
		
		int day = 0;
		while(true) {						
			if(!simulation()) break; //인구이동이 있으면 계속 while 돌면서
			day++; //날짜 늘려주기
		}
		
		System.out.println(day);
	}
	
	static boolean simulation() {
		int[] uNum = new int[N*N];
		int uCnt = -1; //해당 날짜의 simulation에서 생성되는 연합의 수
		for(int i = 0; i<N; i++) {
			for(int j = 0; j<N; j++) {
				if(united[i][j] == -1) { //연합에 속해있지 않다면
                    //bfs해서 연합에 속한 국가(united)업데이트하고
					int c = bfs(i, j, ++uCnt); 
                    //해당 연합의 인구수를 return 받아 uNum에 저장
					uNum[uCnt] = c;
				}
			}
		}
		
		if(uCnt == (N*N-1)) { //모든 국가가 각각의 연합이라면
			return false; //더 이상 인구이동 일어나지 않음
		}
				
		for(int i = 0; i<N; i++) {
			for(int j = 0; j<N; j++) {
				A[i][j] = uNum[united[i][j]]; //인구수 업데이트
				united[i][j] = -1; //연합 리셋
			}
		}
		
		return true;
	}
	
	static int bfs(int r, int c, int uCnt) { //하나의 연합에 속해있는 나라를 찾고 sum을 계산
		int cnt = 0; //연합 안에 있는 나라 수
		int sum = 0; //연합에 속해 있는 모든 인구 수
		Queue<int[]> queue = new LinkedList<>();
		
		queue.offer(new int[] {r,c});
		united[r][c] = uCnt;
		cnt++;
		sum += A[r][c];
		
		int nr, nc;
		while(!queue.isEmpty()) {
			int[] now = queue.poll();
			for(int i = 0; i<4; i++) {
				nr = now[0] + direction[i][0];
				nc = now[1] + direction[i][1];
				if(nr < 0 || nr >= N || nc < 0 || nc >= N || united[nr][nc] != -1) {
					continue;
				}
				int differ = Math.abs(A[nr][nc] - A[now[0]][now[1]]);
				if(differ>=L && differ<=R) { //연합 생김
					queue.offer(new int[] {nr, nc}); //다음 탐색을 위해 queue에 추가
					united[nr][nc] = uCnt; //몇번째 연합인지 체크해두기
					cnt++;
					sum += A[nr][nc];
				}
			}
		}
		//모든 연합을 찾았다면
		return sum/cnt; 
	}
}