[#알고리즘/BFS/[백준]16234번: 인구 이동(java)]

📘 Question

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

💡 Solution

인구 이동 여부는 isMove 메소드를 통해 정한다. 특정 Flag를 세워 해당 Flag가 false라면 인구 이동은 더이상 일어나지 않고, true라면 연합이 이루어지게 되는데 이때 연합을 형성하는 것은 bfs를 통해 해결한다.

💡 Code

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

class Node {
	int x;
	int y;
	
	Node(int x, int y) {
		this.x = x;
		this.y = y;
	}
}

public class BOJ_16234 {
	static int N, L, R;
	static int[][] map;
	static boolean[][] visited; 
	static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    static ArrayList<Node> list = new ArrayList<>();
    static boolean isMove;
    static int cnt;  //인구 이동 발생 횟수

	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());
		
		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] = Integer.parseInt(st.nextToken());
			}
		}
		
		isMove();
		System.out.println(cnt);
		
	}
	
	static void isMove() {
		while(true) {
			isMove = false;
			visited = new boolean[N][N];
			
			for(int i = 0; i < N; i++) {
				for(int j = 0; j < N; j++) {
					if(!visited[i][j]) {
						bfs(i, j);
					}
				}
			}
			// 인구이동이 더이상 발생하지 않으면 종료
			if(!isMove) {
				break;
			}
			// 인구이동이 일어나면 발생일수 추가
			else {
				cnt++;
			}
		}		
	}
	
	static void bfs(int x, int y) {
		Queue<Node> q = new LinkedList<>();
		q.add(new Node(x, y));
		visited[x][y] = true;
		list.add(new Node(x, y));
		
		while(!q.isEmpty()) {
			Node now = q.poll();
			for(int i = 0; i < 4; i++) {
				int nx = now.x + dx[i];
				int ny = now.y + dy[i];
				if(nx >= 0 && ny >= 0 && nx < N && ny < N && !visited[nx][ny]) {
					int diff = Math.abs(map[now.x][now.y] - map[nx][ny]);
					if(diff >= L && diff <= R) {
						isMove = true;
						visited[nx][ny] = true;
						list.add(new Node(nx, ny));
						q.add(new Node(nx, ny));
					}
				}
			}
		}
		
		// BFS 끝난 후 개방된 국가들의 인구 수의 합 구하기
		int sum = 0;
		for(int i = 0; i < list.size(); i++) {
			Node n = list.get(i);
			sum += map[n.x][n.y];
		}
		// 인구이동 결과를 맵에 반영
		for(int i = 0; i < list.size(); i++) {
			Node n = list.get(i);
			map[n.x][n.y] = sum / list.size();
		}
		
		list.removeAll(list);
	}

}