[Java] 백준 16234번 - 인구 이동(BFS, 시뮬레이션)

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

16234번: 인구 이동

 

 

문제

N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다.

오늘부터 인구 이동이 시작되는 날이다.

인구 이동은 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.

• 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루동안 연다.
• 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.
• 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.
• 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.
• 연합을 해체하고, 모든 국경선을 닫는다.

각 나라의 인구수가 주어졌을 때, 인구 이동이 몇 번 발생하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N, L, R이 주어진다. (1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100)

둘째 줄부터 N개의 줄에 각 나라의 인구수가 주어진다. r행 c열에 주어지는 정수는 A[r][c]의 값이다. (0 ≤ A[r][c] ≤ 100)

인구 이동이 발생하는 횟수가 2,000번 보다 작거나 같은 입력만 주어진다.

출력

인구 이동이 몇 번 발생하는지 첫째 줄에 출력한다.

 

 

---

 

 

접근 방법

 

각 땅 (r,c) 에 대해 무한루프를 돌면서 

     - BFS를 이용해 국경선을 서로 열 수 있는 땅을 Queue에 다 넣고, BFS 탐색이 끝나면 인구이동을 해준다. 

     - 모든 칸에 대해 인구이동 여부를 탐색 했으면 다시 처음으로 돌아가서 visited를 초기화 시킨 후 재 탐색한다. (만약 이 단계에서 탐색이 끝났을 때 인구이동이 한 번도 발생하지 않았다면 무한루프를 종료시킨다.)

 

import java.util.*;

class Pair16234{
	Integer r, c;
	public Pair16234(Integer _r, Integer _c) {
		this.r = _r;
		this.c = _c;
	}
	public int getRow() {
		return this.r;
	}
	public int getCol() {
		return this.c;
	}
	
}
public class SM_BOJ16234_인구이동 {

	static int N, L, R, answer;
	static int[][] map, visited; 
	static int[] dr,dc;

	static boolean chk(int a, int b) {
		int sub = Math.abs(a-b);
		if(L <= sub && sub <=R) return true;
		else return false;
	}
	
	static boolean BFS(int r, int c) {
		
		Queue<Pair16234> que = new LinkedList<Pair16234>();
		ArrayList<Pair16234> vec = new ArrayList<Pair16234>();
		int sum = 0;
		
		Pair16234 p = new Pair16234(r,c);
		que.add(p);
		vec.add(p);
		sum = map[r][c];
		
		while(!que.isEmpty()) {
			Pair16234 pair = que.poll();
			int cr = pair.getRow();
			int cc = pair.getCol();
			
			visited[cr][cc] = 1;
			
			for(int i = 0; i<4; i++) {
				int nr = cr + dr[i];
				int nc = cc + dc[i];
				if(nr<1 || nr>N || nc<1 || nc>N || visited[nr][nc]==1) continue;
				
				if(chk(map[cr][cc], map[nr][nc])) {
					visited[nr][nc] = 1;
					Pair16234 p_next = new Pair16234(nr,nc);
					que.add(p_next);
					vec.add(p_next);
					sum += map[nr][nc];
				}
			}
		}
		
		if(vec.size()==1) {
			visited[vec.get(0).getRow()][vec.get(0).getCol()] = 0;
			return false;
		}
		else {
			int avg = sum / vec.size();
			for(int i = 0; i<vec.size(); i++) {
				int row = vec.get(i).getRow();
				int col = vec.get(i).getCol();
				map[row][col] = avg;
			}
			return true;
		}
		
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Scanner sc = new Scanner(System.in);
		dr = new int[4];
		dc = new int[4];
		dr[0] = -1; dr[1] = 0; dr[2] = 1; dr[3] = 0;
		dc[0] = 0; dc[1] = 1; dc[2] = 0; dc[3] = -1;

		N = sc.nextInt();
		L = sc.nextInt();
		R = sc.nextInt();
		
		map = new int[51][51];
		visited = new int[51][51];
		for(int i = 1; i<=N; i++) {
			for(int j = 1; j<=N; j++) {
				map[i][j] = sc.nextInt();
				visited[i][j] = 0;
			}
		}
		
		answer = 0;

		int cnt = 0;	
		while(true) {
			
			if(cnt==N*N) break;
			cnt = 0;
			
			boolean flag = false;
			
            //인구 이동 끝나고 초기화 
			for(int r = 1; r<=N; r++) {
				for(int c = 1; c<=N; c++) {
					visited[r][c] = 0;
				}
			}
			
			for(int i = 1; i<=N; i++) {
				for(int j = 1; j<=N; j++) {

					if(visited[i][j]==0) {
						boolean res = BFS(i,j);		//국경선 열렸으면 true 
						if(res) {
							flag = true;
						}					
						else cnt++;
					}
				}
			}
			
			if(flag) answer++;
		}
		System.out.println(answer);
	}

}