[백준 / BOJ] 16234번 : 인구 이동 (JAVA)

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

16234번: 인구 이동

그룹 만들어서 인구 수 구하기

가장 먼저 해야할 것은 어떤 나라끼리 그룹을 구성하는지 파악하는 것이다. Queue를 사용해서 이미 방문한 곳, 그리고 L과 R 범위를 벗어나는 곳을 제외하고 BFS로 찾아나갔다.

 

이 때 새로운 나라에 방문할 때마다 방문 체크는 물론, 인구를 조사하고(total), 나라 위치를 다시 저장하도록 했다(Queue tmp). 모든 그룹을 조사한 다음에 다시 처음부터 계산하는 것은 비효율적으로 느껴졌기 때문이다. 따라서 한 그룹을 만들면 바로 tmp를 poll하며 방문했던 위치에 인구 평균값 total / tmp.size()을 넣어주었다.

 

map을 중간에 바꾸면 결과가 바뀔 수 있지 않을까? 라는 생각이 들 수도 있지만, group이라는 배열에 방문 체크가 되어 있으면 L, R 비교도 하기 전에 스킵해서 상관 없다.

 

더이상 인구 이동이 없다는 것은 모든 나라가 벽을 걸어잠갔고 L, R 비교 후 nr, nc를 que에 넣는 연산이 한 번도 이루어지지 않았다는 의미이므로 que에 새 나라를 추가하는 데에 flag를 놓았다. 이 flag를 리턴해서 false면 while문을 멈추고, 그렇지 않다면 time을 계속 늘리도록 했다.

 

전체 코드

// 시간 : 576ms
// 메모리 : 294520KB
public class Main {

	static int[] dr = {-1,0,1,0};
	static int[] dc = {0,-1,0,1};
	static int R;
	static int L;
	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		L = Integer.parseInt(st.nextToken());
		R = Integer.parseInt(st.nextToken());
		
		int[][] map = new int[N][N];
		
		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());
			}
		}
		
		int time = 0;
		while(moving(map)) {
			time++;
		}
		System.out.println(time);
	}
	
	static boolean moving (int[][] map) {
		
		boolean flag = false;
		int N = map.length;
		boolean[][] group = new boolean[N][N];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if(group[i][j]) continue;
				Queue<int[]> que = new LinkedList<>();
				que.offer(new int[] {i, j});
				group[i][j] = true;
				
				int total = 0;
				Queue<int[]> tmp = new LinkedList<>();
				while(!que.isEmpty()) {
					int[] cur = que.poll();
					total += map[cur[0]][cur[1]];
					tmp.offer(cur);
					
					for (int d = 0; d < 4; d++) {
						int nr = cur[0] + dr[d];
						int nc = cur[1] + dc[d];
						
						if(nr >= N || nc >= N || nr < 0 || nc < 0 || group[nr][nc]) continue;
						int diff = Math.abs(map[cur[0]][cur[1]] - map[nr][nc]);
						if(diff >= L && diff <= R) {
							group[nr][nc] = true;
							que.offer(new int[] {nr, nc});
							flag = true;
						}
					}
				}
				
				int people = total / tmp.size();
				while(!tmp.isEmpty()) {
					int[] cur = tmp.poll();
					map[cur[0]][cur[1]] = people;
				}
			}
		}
		return flag;
	}

}