[16234] 인구 이동

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

16234번: 인구 이동

---

import java.util.Scanner;

class Main {

	static int N, L, R, COUNT=0, total, union, people;
	static int[][] arr;
	static boolean[][] visited, visited2;
	static int[][] dir = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };
	static boolean flag;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		L = sc.nextInt();
		R = sc.nextInt();
		arr = new int[N][N];

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

		flag = true;

		while (flag) {
			COUNT++;
			flag = false;
			visited = new boolean[N][N];
			visited2 = new boolean[N][N];

			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (!visited[i][j] && !visited2[i][j]) {
						for (int k = 0; k < 4; k++) {
							int nx = i + dir[k][0];
							int ny = j + dir[k][1];
							if (isInside(nx, ny) && !visited[nx][ny] && !visited2[nx][ny] && Math.abs(arr[i][j] - arr[nx][ny]) >= L
									&& Math.abs(arr[i][j] - arr[nx][ny]) <= R) {
//								System.out.println("----------" + arr[i][j] + " 에서 DFS 진행중----------" + " 현재시간 : " + COUNT);
								total = 0; // 연합의 인구수
								union = 0; // 연합을 이루고 있는 칸의 개수
								DFS(i, j);
								people = total / union;
								DFS2(i, j);
								flag = true;
//								print();
								break;
							}
						}
					}
				}
			}
			
		}

		System.out.println(COUNT-1);
	}

	public static void DFS2(int x, int y) {
		visited2[x][y] = true;
		arr[x][y] = people;

		for (int i = 0; i < 4; i++) {
			int nx = x + dir[i][0];
			int ny = y + dir[i][1];

			if (isInside(nx, ny) && visited[nx][ny] && !visited2[nx][ny]) {
				DFS2(nx, ny);
			}
		}

	}

	public static void print() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				System.out.print(arr[i][j] + " ");
			}
			System.out.println();
		}
		System.out.println();
	}

	public static void DFS(int x, int y) {
		visited[x][y] = true;
		total += arr[x][y];
		union++;

		for (int i = 0; i < 4; i++) {
			int nx = x + dir[i][0];
			int ny = y + dir[i][1];

			if (isInside(nx, ny) && !visited[nx][ny] && Math.abs(arr[x][y] - arr[nx][ny]) >= L && Math.abs(arr[x][y] - arr[nx][ny]) <= R) {
				DFS(nx, ny);
			}
		}
	}

	public static boolean isInside(int x, int y) {
		if (x >= 0 && x < N && y >= 0 && y < N)
			return true;
		else
			return false;
	}
}

---

저는 이 문제를 DFS와 DFS2를 사용해서 풀었습니다. DFS는 인구이동이 이루어 졌을 때 people을 구하기 위해서 연합의 인구수 total과 연합을 이루고 있는 칸의 개수 union을 구하는 함수이고, DFS2는 구한 people을 인구이동이 일어난 나라에게 저장해주는 함수입니다. 함수이름을 비슷하게 해서 헷갈릴 수 있지만 while 문안에 DFS 먼저 수행하고 그 다음에 DFS2를 수행한다고 생각하면 쉽게 이해할 수 있습니다.

[문제 풀이]

1. 처음에 flag 를 true 로 설정해주어서 while문에 들어가게 합니다. while문 안에서는 두나라의 인구수의 차가 L명 이상 R명 이하이면 flag를 true로 바꿔주어서 다시 연산을 수행하게 하고, 만약에 아니라면 flag를 false로 바꿔주어서 반복문을 빠져나오게하고 인구이동이 몇번 발생했는지 출력합니다.

2. 처음에 0,0부터 N,N 까지 반복문을 수행하면서 인접한 나라의 인구수의 차를 확인합니다. 인구이동이 가능하면 DFS를 먼저 시행하는데 DFS는 연합의 인구수를 나타내는 total 과 연합을 이루고 있는 칸의 개수 union을 계산해주는 함수입니다.

3. DFS 를 실행하면 total 과 union 이 구해졌으므로 인구이동 하게 될 사람들의 수 people 을 계산할 수 있으므로 계산하고 DFS2를 하여 다시 arr에 계산된 people을 저장 합니다.

4. 인구이동을 수행했으므로 flag 를 true로 바꿔줍니다.