[backjoon]16234 인구 이동 java

www.acmicpc.net/problem/16234

16234번: 인구 이동

Gold 5

완전 탐색! DFS도 되고 BFS도 되지만 난 BFS로 풀이!

1. 완전 탐색(for 문 2번 돌리기)로 동서남북을 확인하며 범위내에 해당하는지 확인

1) 해당하면 queue에 넣어서 인구 이동이 가능한지를 탐색(BFS나 DFS사용) 가능하다면 flag를 둬서 가능함을 표시(나중에 인구 이동 발생 횟수를 증가 시키기 위함)

2) 이동 가능한 인구 수 의 합계를 구하기 위해 변수를 정하고 인구수 더하기

2. queue에 더 이상 안 들어가면 총 합계2) 에 면적 나누기

3. 완전 탐색이 끝나면 flag 가 true 면 answer++;

false면 탐색 종료.

 

인구 이동이 일어난 날 들을 구해야하는데, 처음엔 인구 이동에 횟수인줄 알았다.

인구 이동 횟수 카운트를 위해 사용하던 걸 잘 응용하면 쉽게 풀 수 있다고 생각한다.

나의 경우엔 카운트 잘 해 놓고 막판에 헷갈린 편 ㅜㅜ

귀찮아서 queue 남발했더니 코드가 영 지저분하긴하다...

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

class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st; 
		st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int L = Integer.parseInt(st.nextToken());
		int R = Integer.parseInt(st.nextToken());
		int[][] dir = {{-1,0}, {1, 0}, {0, 1}, {0, -1}};
		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++) {
				int cur = Integer.parseInt(st.nextToken());
				map[i][j] = cur;
			}
		}
		int answer = 0;
		boolean flag = true;
		
		while(flag){
			
			flag = false;
			boolean[][] marked = new boolean[N][N];
			
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
			
					if(marked[i][j]) continue;
					marked[i][j] = true;
					int sum = map[i][j];
					
					Queue<Dot> queue = new LinkedList<Dot>();//연결된 영역을 알기 위한 queue
					Queue<Dot> queueInsert = new LinkedList<Dot>(); // 인구 분배를 위한 queue
					queue.add(new Dot(i, j));
					queueInsert.add(new Dot(i, j));
	
					while(!queue.isEmpty()) {
						Dot d = queue.poll();
						for (int k = 0; k < 4; k++) {
							int nextR = d.row + dir[k][0];
							int nextC = d.col + dir[k][1];
							
							if(nextR < 0 || nextC < 0 || nextR >= N || nextC >=N) continue;
							if(marked[nextR][nextC]) continue;
							
							// 적절한 값인지 알기 위해 검증하는 부분. 상대적이라 계속 변해서 위치가 중요
							int value = Math.abs(map[nextR][nextC] - map[d.row][d.col]);
							if(value < L || value > R) continue;
							
							marked[nextR][nextC] = true;
							queue.add(new Dot(nextR, nextC));
							queueInsert.add(new Dot(nextR, nextC));
							sum += map[nextR][nextC];
							flag = true;
						}
					}
					sum /=queueInsert.size();
					while(!queueInsert.isEmpty()) {
						Dot d = queueInsert.poll();
						map[d.row][d.col] = sum;
					}
				}
			}
			if(flag) answer++;
		}
		System.out.println(answer);
	}
}
class Dot{
	int row;
	int col;
	Dot(int row, int col){
		this.row = row;
		this.col = col;
	}
}