[BOJ-16234] 인구이동 -Java

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

16234번: 인구 이동

package 시뮬레이션_review;

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

public class boj_16234_인구이동 {
	static int N,L,R,result,map[][];
	static int dx[]= {0,0,-1,1};
	static int dy[]= {-1,1,0,0};
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		result=0;
		N=Integer.parseInt(st.nextToken());
		L=Integer.parseInt(st.nextToken());
		R=Integer.parseInt(st.nextToken());
		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());
			}
		}
		solve();
		System.out.println(result);
		
	}
	private static void solve() {
		while(true) {
			int sectionNo=1;
			int [][] section = new int [N][N];
			List <int[]> totalInfo = new ArrayList<>(); // 몇번연합, 연합을 이루는 칸갯수, 연합 인구수
			
			for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++) {
					if(section[i][j]!=0) continue; //이미 간곳이라면 
					if(bfs(section,totalInfo,sectionNo,i,j)) sectionNo++; //연합이 만들어지면 숫자++
				}
			}
			if(sectionNo==1) break; //연합이 더이상 없으면
			divPopoulation(totalInfo,section);
			result++;
		}
		
	}
	private static void divPopoulation(List<int[]> totalInfo, int[][] section) {
		int population[]=new int[totalInfo.size()];
		for(int i=0; i<totalInfo.size(); i++) {
			int []Info=totalInfo.get(i);
			population[i]=Info[2]/Info[1];
		}
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				if(section[i][j]==-1 || section[i][j]==0) continue;
				else map[i][j]=population[section[i][j]-1];
			}
		}
		
	}
	private static boolean bfs(int[][] section, List<int[]> totalInfo, int sectionNo, int x, int y) {
		section[x][y]=-1;//우선 방문처리
		int totalPopulation=map[x][y];
		int sectionCnt=1;
		Queue <int[]> queue = new LinkedList<>();
		
		queue.offer(new int[] {x,y});
		
		while(!queue.isEmpty()) {
			int []point=queue.poll();
			
			for(int d=0; d<4; d++) {
				int nx=point[0]+dx[d];
				int ny=point[1]+dy[d];
				
				if(nx<0 || ny<0 || nx>=N || ny>=N || section[nx][ny]!=0) continue;
				if(!isBound(point[0],point[1],nx,ny)) continue; //L,R확인
				section[nx][ny]=sectionNo;
				sectionCnt++;
				totalPopulation+=map[nx][ny];
				queue.offer(new int[] {nx,ny});
			}
		}
		
		if(map[x][y]==totalPopulation) return false; //연합 형성이 안됬으면 
		else {
			totalInfo.add(new int[] {sectionNo, sectionCnt, totalPopulation});
			section[x][y]=sectionNo;// 연합에 넣고
			return true; //true
		}
	}
	private static boolean isBound(int x, int y, int nx, int ny) {
		int check=Math.abs(map[x][y]-map[nx][ny]);
		if(L<=check && R>=check) return true;
		return false;
	}
}

 

소요시간 : 55분

 

프로젝트 때문에 알고리즘을 너무 오랜만에 풀었습니다...

오랜만에 푸니까 뭔가 잘 안 풀리네요. 내일부터는 다시 하루에 한 문제 시작합니다!

 

로직을 살펴보면

 

1. BFS를 통해 연합을 만들어 줍니다.

2. 연합을 만들면서 각 연합이 몇 개의 칸으로 이루어졌는지, 총인구수가 몇인지 저장해줍니다.

3. 만약 연합이 있다면 위에서 구한 내용을 토대로 map을 바꿔줍니다.

 

주의사항 - 모든 연합을 구하고 나서 map을 바꿔야 합니다.

              연합을 구하는 도중에 map을 바꾸면 원래 연합이어야 하는데 연합이 안되거나,

              연합이 아닌데 연합이 되는 경우가 생깁니다.