[백준/16234/Java] 인구이동

 

 

문제:

www.acmicpc.net/problem/16234

16234번: 인구 이동

 

문제를 먼저 풀고 오시는 것을 추천합니다.

 

 

문제분석

NxN크기의 정사각형 땅이 있고, 각 나라에는 A[r][c]명이 살고 있습니다.

 

인구이동은 다음과 같이 진행되고, 더 이상 인구이동이 불가능할 때까지 지속됩니다.

- 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루동안 엽니다.
- 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으며, 그 나라들을 오늘 하루 동안 연합이라고 합니다.
- 연합은 서로 인구이동을 시작하고, 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 됩니다. 소수점 이하는 버립니다.
- 연합을 해체하고, 모든 국경선을 닫습니다. 첫번째 단계부터 다시 시작하고 연합이 존재하지 않으면 종료합니다.

 

입력

첫째 줄에 N, L, R(땅 크기 1<=N<=50, 인구차이 1<=L<=R<=100)이 주어집니다.

둘째 줄부터 N개의 줄에 각 나라의 인구수가 주어집니다.  (0<=A[r][c]<=100)

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

 

출력

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

 

풀이

1. 인접한 국가들 중 인구차이가 L명 이상, R명 이하인 나라가 존재하는지 (0, 0)부터 (N-1, N-1)까지 탐색합니다.

2. 나라 1개라도 찾으면 BFS로 인접한 국가들을 탐색하고 연합으로 지정합니다.

   연합은 여러 나라이므로 배열에 저장합니다. 배열의 크기가 곧 연합를 이루고 있는 나라의 총 개수입니다.

   나라를 하나씩 찾을 때마다 인구수를 더합니다.

3. 인구이동이 발생하면 인구이동수에 1을 더하고 1번부터 다시 시작합니다.

4. 연합이 구성된 적이 없으면 인구이동수를 출력하고 종료합니다.

 

예제풀이

20 <= 인구수 <= 50의 조건을 가지고 있는 예제를 보겠습니다.

 

(0, 0)에서 인접한 국가가 인구차이 조건을 만족하므로 연합을 구성하고 인구이동을 합니다.

 

더 이상 연합을 구성할 수 없으므로 인구이동수 1을 출력합니다.

 

 

소스

입력받은 값 외에 연합을 찾기 위하여 BFS로 탐색하고 이 때 방문배열 V을 선언하여 사용하였습니다.

BFS 탐색하면서 연합국가 위치정보를 List<int[]>형 변수인 uList에 넣고 인구총합은 int형 변수인 sum에 저장하였습니다..

인구이동을 하면 인구평균수는 sum / uList.size()로 구할 수 있습니다.

그리고 평균값은 uList에 저장된 int[] 위치정보로 설정합니다.

int[0]은 r, int[1]은 c 정보로 위치정보를 int[2] 형태로 저장하였습니다.

따라서 이렇게 국가 위치를 가져와서 평균값 avg를 설정할 수 있습니다.

for (int[] u : uList)
	A[u[0]][u[1]] = avg;

 

연합을 이룰 수 있는 국가인지 판단하기 위하여 상하좌우를 검색하는 existUnion 함수를 선언하였습니다.

그리고 인구차이 조건을 검색하는 isUnion 함수를 선언하였고 (기준국가 인구수 - 상하좌우 인구수)의 절대값을 구하여 diff 변수에 저장하고  L <= diff <= R을 만족하는지 계산하였습니다.

 

 

아래는 전체 소스입니다.

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

public class Main {
	static int N;
	static int A[][];
	static int V[][];

	static int L, R;

	static int ANS = 0;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.valueOf(st.nextToken());
		L = Integer.valueOf(st.nextToken());
		R = Integer.valueOf(st.nextToken());

		A = new int[N][N];
		V = new int[N][N];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				A[i][j] = Integer.valueOf(st.nextToken());
			}
		}

		// 인접 인구수 L <= A[r][c] <= R이면 국경선 오픈
		// 인구이동 (연합의 인구수) / (연합을 이루고 있는 칸의 개수) : BFS
		boolean flag = false;
		do {
			// 초기화
			flag = false;

			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					// 연합이 존재하는지 확인
					if (V[i][j] == 0 && existUnion(i, j))
						if (bfs(i, j) == true) {
							flag = true; // 연합이 한 번이라도 구성되면 flag를 true로 설정
//							print();
						}
				}
			}

			if (flag == true) {
				ANS++;

				// 초기화
				for (int i = 0; i < N; i++) {
					Arrays.fill(V[i], 0);
				}
			}

		} while (flag == true);

		System.out.println(ANS);
	}

	private static boolean existUnion(int r, int c) {
		// 인접한 국가 중 연합이 될 수 있는 국가가 있는지 탐색
		if (r - 1 >= 0 && V[r - 1][c] == 0 && isUnion(A[r][c], r - 1, c) == true)
			return true;
		if (r + 1 < N && V[r + 1][c] == 0 && isUnion(A[r][c], r + 1, c) == true)
			return true;
		if (c - 1 >= 0 && V[r][c - 1] == 0 && isUnion(A[r][c], r, c - 1) == true)
			return true;
		if (c + 1 < N && V[r][c + 1] == 0 && isUnion(A[r][c], r, c + 1) == true)
			return true;
		return false;
	}

	private static boolean isUnion(int count, int r, int c) {
		// 인구수가 L <= A[r][c] <= R인지 비교
		int diff = Math.abs(count - A[r][c]);
		if (L <= diff && diff <= R)
			return true;
		return false;
	}

	private static boolean bfs(int r, int c) {
		List<int[]> uList = new ArrayList<int[]>();	// 연합 국가 목록
		int sum = 0;	// 인구 총합

		Queue<int[]> q = new LinkedList<int[]>();

		q.add(new int[] { r, c });
		V[r][c] = 1;
		uList.add(new int[] { r, c });
		sum = A[r][c];

		int[] cur;
		while (q.isEmpty() == false) {
			cur = q.poll();
			r = cur[0];
			c = cur[1];

			if (r - 1 >= 0 && V[r - 1][c] == 0 && isUnion(A[r][c], r - 1, c) == true) {
				V[r - 1][c] = 1;
				uList.add(new int[] { r - 1, c });	// 국가 추가
				sum += A[r - 1][c];	// 인구수 추가
				q.add(new int[] { r - 1, c });
			}
			if (r + 1 < N && V[r + 1][c] == 0 && isUnion(A[r][c], r + 1, c) == true) {
				V[r + 1][c] = 1;
				uList.add(new int[] { r + 1, c });
				sum += A[r + 1][c];
				q.add(new int[] { r + 1, c });
			}
			if (c - 1 >= 0 && V[r][c - 1] == 0 && isUnion(A[r][c], r, c - 1) == true) {
				V[r][c - 1] = 1;
				uList.add(new int[] { r, c - 1 });
				sum += A[r][c - 1];
				q.add(new int[] { r, c - 1 });
			}
			if (c + 1 < N && V[r][c + 1] == 0 && isUnion(A[r][c], r, c + 1) == true) {
				V[r][c + 1] = 1;
				uList.add(new int[] { r, c + 1 });
				sum += A[r][c + 1];
				q.add(new int[] { r, c + 1 });
			}
		}

		// 연합 내 인구 이동
		int avg = sum / uList.size();
		for (int[] u : uList)
			A[u[0]][u[1]] = avg;
		if (uList.size() < 2)
			return false;
		return true;
	}

	private static void print() {
		for (int i = 0; i < N; i++) {
			System.out.println(Arrays.toString(A[i]));
		}
		System.out.println();
	}
}