인구이동


백준 [16234] 인구이동

문제보기
Alt text

풀이

  • 주의사항 : movePopul()마다 ans를 체크하면 안되고 united() 전체가 끝났을 때를 한번으로 세야함
  • united() : bfs 방식으로 연합 체크
  • movePopul() : 같은 연합끼리 인구이동

소스코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static int N, L, R, ans;
	static int[][] map;
	static int[] dx = { -1, 1, 0, 0 };
	static int[] dy = { 0, 0, -1, 1 };
	static Queue<int[]> queue;
	static int[][] visited;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		L = sc.nextInt();
		R = sc.nextInt();
		map = new int[N][N];
		queue = new LinkedList<>();
		ans = 0;

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				map[i][j] = sc.nextInt();
			}
		}

		while (true) {
			visited = new int[N][N];
			if (!united()) {
				break;
			} else {
				ans++;
			}
		}

		System.out.println(ans);
	}

	public static boolean united() {
		boolean flag = false;
		int idx = 1;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				int popul = 0;
				int cnt = 0;
				if (visited[i][j] != 0)
					continue;
				boolean chk = false;
				for (int k = 0; k < 4; k++) {
					int x = i + dx[k];
					int y = j + dy[k];

					if (isRange(x, y) && visited[x][y] == 0) {
						int diff = Math.abs(map[x][y] - map[i][j]);
						if (diff < L || diff > R)
							continue;
						flag = true;
						queue.add(new int[] { x, y });
						visited[x][y] = idx;
						popul += map[x][y];
						cnt++;
						chk = true;
					}
				}
				if (chk) {
					popul += map[i][j];
					cnt++;
					visited[i][j] = idx;
				}

				while (!queue.isEmpty()) {
					int[] q = queue.poll();
					for (int k = 0; k < 4; k++) {
						int x = q[0] + dx[k];
						int y = q[1] + dy[k];

						if (isRange(x, y) && visited[x][y] == 0) {
							int diff = Math.abs(map[x][y] - map[q[0]][q[1]]);
							if (diff < L || diff > R)
								continue;
							queue.add(new int[] { x, y });
							visited[x][y] = idx;
							popul += map[x][y];
							cnt++;
						}
					}
				}
				if (cnt > 0) {
					movePopul(idx, popul, cnt);
				}
				idx++;
			}
		}
		return flag;
	}

	public static void movePopul(int idx, int popul, int cnt) {
		int population = popul / cnt;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (visited[i][j] == idx)
					map[i][j] = population;
			}
		}
	}

	public static boolean isRange(int x, int y) {
		return x >= 0 && y >= 0 && x < N && y < N;
	}
}