[백준 16234] 인구 이동 (JAVA)

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

16234번: 인구 이동

 

bfs를 이용하여 해결할 수 있었다!

방문 표시 배열과, 연합 국가 리스트를 사용하여

0,0부터 포문을 돌면서 방문한 적이 없는 국가에 대한 bfs를 실행한다.

인접한 국가와  l <= ★ <= r 차이를 가진 곳들을 연합 국가 리스트에 add 하고 해당 국가들의 인구 수를 sum에 넣는다.

그렇게  bfs가 끝나면 연합 국가 리스트의 수가 1보다 클 경우에는 연합 국가가 있는 것이므로, 

연합 국가에 해당하여 인구수를 sum/ 리스트 수 로 바꾸어 준다. (change함수)  또한 check 변수의 값을 true로 변경하여

일 수(result값)를 ++하게끔 한다!

 

 

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;

public class test16234 {

	static int n, l, r, result = 0;
	static int[][] arr;
	static boolean check = false;
	static int[] dx = { 1, -1, 0, 0 };
	static int[] dy = { 0, 0, 1, -1 };
	static ArrayList<Node> list;
	static boolean[][] visited;

	static class Node {
		int x, y;

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

	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());
			}
		}

		simul();

		System.out.println(result);
	}

	static void simul() {
		while (true) {
			check = false;
			visited = new boolean[n][n];
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					if (!visited[i][j]) {
						int sum = bfs(i, j);
						if (list.size() > 1) {
							change(sum);
							check = true;
						}
					}

				}
			}

			if (!check)
				break;
			result++;
		}
	}

	static void change(int sum) {
		int value = sum / list.size();
		for (Node node : list) {
			arr[node.x][node.y] = value;
		}
	}

	static int bfs(int x, int y) {
		list = new ArrayList<>();
		Queue<Node> q = new LinkedList<>();
		q.add(new Node(x, y));

		int sum = arr[x][y];
		list.add(new Node(x, y));
		visited[x][y] = true;

		while (!q.isEmpty()) {
			Node node = q.poll();

			for (int i = 0; i < 4; i++) {
				int xx = node.x + dx[i];
				int yy = node.y + dy[i];

				if (xx < 0 || yy < 0 || xx >= n || yy >= n || visited[xx][yy])
					continue;
				int dist = Math.abs(arr[node.x][node.y] - arr[xx][yy]);
				if (dist >= l && dist <= r) {
					sum += arr[xx][yy];
					q.add(new Node(xx, yy));
					list.add(new Node(xx, yy));
					visited[xx][yy]=true;
				}
			}
		}

		return sum;
	}

}