[JAVA] 백준 16234번 - 인구 이동

 

풀이방법

- 그래프 탐색 알고리즘을 이용해서 푸는 문제였다. 그 중 BFS 알고리즘을 사용해서 풀었다.

- BFS 알고리즘을 이용한 이유는 각 좌표에서 이웃한 국가들, 그리고 연합과 이웃한 국가들 중에서 연합이 될 수 있는 좌표들만 탐색하면 되기 때문이다. (전체 탐색 필요 X)

- 전체 map을 첫 좌표 (0,0) 부터 마지막 좌표 (n,n) 까지 탐색 하면서 BFS알고리즘을 이용해 인구 수 차이가 L~R 사이인 나라를 찾고 union 큐에 넣어줬다.

 

>  처음엔 map과 같은 2차원 배열을 만들어서 연합이면 map[i][j] = 1로 설정해서 union 정보를 저장하려 했으나 탐색하는 과정을 한번 더 거쳐야 하는 복잡하고 번거로운 방법이라 생각하여 큐로 방법을 바꾸었다.

>  큐를 사용하면 그때 그때 연합 좌표들을 저장(q.offer)하고 뽑아오는게(q.poll) 편리하다. 

 

- 탐색 과정에서 연합 국가가 존재하면 플래그 isUnion을 true로 설정하고 없다면 false로 설정했다.

- 또한 연합인 국가들의 인구수를 전부 sum에 더했다.

- 탐색을 마치면 찾았던 연합들의 전체 인구 수 sum과 전체 연합 수 size를 나누어 각 나라에 재 배치 할 인구 pop을 구하고

- union 큐에서 연합 좌표들을 하나씩 poll 하여 해당 좌표의 인구 수를 pop으로 다시 저장했다.

- 이 과정을 연합이 없을 때 까지 (각 나라의 인구 차이가 L~R사이에 없을 때 까지 -> isUnion = false) 반복하며 

- 반복 횟수 count를 증가시켰다.

- 연합이 없어 isUnion = false 로 반복문이 break되면 count를 출력한다.

---

Code

import java.io.*;
import java.util.*;

public class Main {

	public static int[][] map;
	public static boolean[][] visit;
	public static int n;
	public static int l, r;
	public static int[] dx = {1,-1,0,0};
	public static int[] dy = {0,0,1,-1};
	public static boolean isUnion;
	public static void main(String[] args) throws Exception  {
	
		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];
		int count = 0;
		
		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());
			}
		}
		
		while(true) {
			visit = new boolean[n][n];
			isUnion = false;
			
			for(int i = 0; i<n; i++) {
				for(int j = 0; j<n; j++) {
					findUnion(i,j);
				}
			}
			if(!isUnion) {
				break;
			}
			count++;
		}
		System.out.println(count);
		
	}
	public static void findUnion(int startX, int startY) {
		if(visit[startX][startY] == true) {
			return;
		}
		Queue<int[]> q = new LinkedList<>();
		Queue<int[]> union = new LinkedList<>();
		q.offer(new int[] {startX, startY});
		visit[startX][startY] = true;
		union.offer(new int[] {startX,startY});
		int sum = 0;
		sum = sum + map[startX][startY];
		
		while(!q.isEmpty()) {
			int now[] = q.poll();
			int nowX = now[0];
			int nowY = now[1];
			
			for(int i = 0; i<4; i++) {
				int nextX = nowX + dx[i];
				int nextY = nowY + dy[i];
				if(nextX < 0 || nextY < 0 || nextX >=n || nextY >=n) {
					continue;
				}
				if(visit[nextX][nextY] == true) {
					continue;
				}
				int dif = Math.abs(map[nextX][nextY] - map[nowX][nowY]);
				if(dif>=l && dif<=r) {
					isUnion = true;
					union.offer(new int[] {nextX,nextY});
					q.offer(new int[] {nextX,nextY});
					sum = sum + map[nextX][nextY];
					visit[nextX][nextY] = true;
				}
			}
		}
		popRelocation(union, sum);
	}
	
	public static void popRelocation(Queue<int[]> union, int sum) {
		int size = union.size();
		int pop = sum/size;
		for(int i = 0; i<size; i++) {
			int[] loc = union.poll();
			int locX = loc[0];
			int locY = loc[1];
			map[locX][locY] = pop;
		}
	}

}