[백준] 16234번 인구 이동 (bfs, 시뮬레이션, java)

 

www.acmicpc.net/problem/16234

16234번: 인구 이동

arraylist는 검사 시작점과 연합국인 곳들의 좌표가 들어가는 리스트이다.

 

1. 방문 안된 곳에서 상하좌우를 검사하면서 경계를 열 수있는 곳을 검사한다. 연합국이 되면 sum+=연합국 인구수,  cnt(연합국에 들어가는 개수)+1해주고 arraylist에 새로운 연합국의 좌표를 넣어준다.

 

2. 시작한 곳에서 bfs로 최대한 검사할 수 있는 곳까지 다 검사가 끝나면 arraylist 좌표에 해당하는 모든 곳의 인구수를 변경한다. 

 

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Pos{
	int y,x;

	public Pos(int y, int x) {
		super();
		this.y = y;
		this.x = x;
	}
	
}

public class Main {
	static int n,l,r;
	static int[] xpos= {0,0,1,-1};
	static int[] ypos= {1,-1,0,0};
	static int[][] map;
	static boolean[][] vis;
	static boolean isPossible=true;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();//나라수
		l=sc.nextInt();//l 이상
		r=sc.nextInt();//r 이하
		map=new int[n][n];
		vis=new boolean[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				map[i][j]=sc.nextInt();
			}
		}
		
		//인구 이동 못할 때까지 이동한다
		int answer=0;
		while(true) {
			isPossible=false;
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					vis[i][j]=false;
				}
			}
			
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					if(vis[i][j]==false) {
						int sum=map[i][j];
						int cnt=1;
						ArrayList<Pos> arr=new ArrayList<>();
						arr.add(new Pos(i,j));
						Queue<Pos> q=new LinkedList<Pos>();
						q.add(new Pos(i,j));
						vis[i][j]=true;
						while(q.size()!=0) {
							Pos cur=q.poll();
							int y=cur.y;
							int x=cur.x;
							
							for (int k = 0; k < 4; k++) {
								int yy=y+ypos[k];
								int xx=x+xpos[k];
								if(xx<0 || yy<0 || xx>=n || yy>=n)continue;
								if(vis[yy][xx])continue;
								int diff=Math.abs(map[y][x]-map[yy][xx]);
								if(diff>=l && diff<=r) {
									isPossible=true;//연합 가능한 나라가 있음
									vis[yy][xx]=true;
									sum+=map[yy][xx];
									cnt+=1;
									q.add(new Pos(yy,xx));
									arr.add(new Pos(yy,xx));//리스트에다 넣어준다.
								}
							}
						}
						//연합할 수 있는 나라 다 구했음
						for (int k = 0; k < arr.size(); k++) {
							int yy=arr.get(k).y;
							int xx=arr.get(k).x;
							map[yy][xx]=sum/cnt;
						}
						
						
					}
				}
			}
			//연합할 수 있는 나라가 없다면 
			if(isPossible==false)break;
			answer+=1;
		}
		System.out.println(answer);
		
	}
}