BOJ 16234 인구이동

16234번: 인구 이동

삼성역테에 나온 문제답게 시뮬레이션+bfs였고 디버깅이 오래걸렸다. 그래도 조건만 잘 숙지하면 그렇게 어려운 문제는 아니었다. (근데 난 이 조건을 처음에 잘못봐가지고 디버깅하는데 오래걸림 ^^;;)

 

일단 나의 풀이는 아래와 같다

1.  bfs 돌기전에, 미리 국경이 열릴 나라들(1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100) 을 모두 체크해준다 -> 여기서 체크된 나라가 0 이면 인구이동 끝.
2.  체크된 나라 && visited가 false인 나라만 bfs를 돈다.
3. bfs를 돌면서 visited체크가 안되어있고, 현재 탐색중인 나라 (country[x][y])와 국경이 열러 연합국이 된다면 큐에 넣어주고, 국가 인구를 count한다.
4. bfs가 끝났으면 큐에서 연합국을 빼서 인구를 변경해준다. 

시간복잡도는

bfs에 걸리는 시간복잡도 O(n^2)에, 국경 체크 메서드에서 걸리는 시간복잡도 O(n^2)을 더해서 O(n^4)이다.

 

 

 

국경체크메서드

위아래양옆에서 국경이 하나라도 열리면 true로 처리해준다.

	private static void checking(int N, int L, int R) { //국경 열린 것 체크해주는 함수 
		for(int i=0; i<N ;i++) {
			for(int j=0; j<N; j++) {
				boolean flag2=false;
				for(int m=0; m<4;m++) {
					int nx=i+dx[m];
					int ny=j+dy[m];
					if(nx<0 || ny<0 || nx>=N || ny>=N) continue;
					if(check[nx][ny]) continue;
					int num =Math.abs(country[nx][ny]-country[i][j]);
					if(num<=R && num>=L) {
						check[nx][ny]=true;
						flag2=true;
						flag=true;
					}
				}
				if(flag2) check[i][j]=true;
			}
		}
	}
	

 

인구이동 메서드

큐에 들어간 모든 국가의 인구를 변경해준다. 

	private static void change_poupluation(int num) { //인구 이동해주는 함수 
		while(!store.isEmpty()) {
			location peekNum=store.poll();
			int x = peekNum.x; 
			int y = peekNum.y;
			country[x][y]=num; 
		}
	}

 

BFS 

기본 bfs에 연합국인지 아닌지 체크 추가, 연합국 큐에 넣는 연산 추가 

private static void bfs(int N , int mx, int my, int L, int R) {
		int count=1;
		int pop_sum=country[mx][my];
		visit[mx][my]=true; 
		store.add(new location(mx,my));
		q.add(new location(mx,my));
		while(!q.isEmpty()) {
			location peekNum=q.poll();
			int x = peekNum.x;
			int y = peekNum.y;
			for(int i=0; i<4;i++) {
				int nx=x+dx[i];
				int ny=y+dy[i];
				if(nx<0 || ny<0 || nx>=N || ny>=N) continue;
				int num = Math.abs(country[nx][ny]-country[x][y]);
				if(visit[nx][ny]!=true && (num>=L && num <=R)) {
					//visit이 안되어있고, 현재 bfs 탐색중인 노드인 country[x][y] 사이와의 국경이 열려있을 때 
					q.add(new location(nx,ny)); // bfs큐에 넣기 
					store.add(new location(nx,ny)); //인구 수 변동 될 큐에 넣기 
					visit[nx][ny]=true;
					count++; //국가 수 
					pop_sum+=country[nx][ny]; //인구 수 
				}
			}

		}
		change_poupluation(pop_sum/count);
	}  
}

 

 

전체 코드

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

class location
{
	public int x;
	public int y;
	
	public location(int x, int y) {
		this.x=x;
		this.y=y;
	}
}

public class Main {
	private static int[][]country;
	private static boolean[][]visit;
	private static boolean[][]check;
	private static Queue<location>q= new LinkedList<location>();
	private static Queue<location>store= new LinkedList<location>();
	private static boolean flag;
	static int[]dx = {-1,1,0,0};
	static int[]dy= {0,0,-1,1};
	
	public static void main(String args[])throws IOException
	{
		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());
		country = new int[n][n];
		visit = new boolean[n][n];
		check = new boolean[n][n];
		String[]s;
		for(int i=0; i<n;i++) {
			s = br.readLine().split(" ");
			for(int j=0; j<n; j++) {
				country[i][j]=Integer.parseInt(s[j]);
			}
		}
		int cnt=0;
		while(true) {
			flag=false;
			checking(n,L,R); //탐색 할 노드 체크해주기! 위아래좌우에 열린 국경이 있는 국가들 모두 체크 
			if(!flag) break; // 국가가 하나도 안체크되어있으면 끝 
			for(int i = 0; i<n;i++) { // 체크된 국가 bfs돌기 
				for(int j=0; j<n; j++) {
					if(check[i][j] && visit[i][j]!=true) { 
						bfs(n,i,j,L,R);
					}
				}
			}
			for(boolean i[] : visit) {
				Arrays.fill(i, false);}
			for(boolean j[]: check) {
				Arrays.fill(j, false); 
			}
			
			cnt++; //이동 횟수 증가 
		
		}
		System.out.println(cnt);
	}
	
	
	private static void checking(int N, int L, int R) { //국경 열린 것 체크해주는 함수 
		for(int i=0; i<N ;i++) {
			for(int j=0; j<N; j++) {
				boolean flag2=false;
				for(int m=0; m<4;m++) {
					int nx=i+dx[m];
					int ny=j+dy[m];
					if(nx<0 || ny<0 || nx>=N || ny>=N) continue;
					if(check[nx][ny]) continue;
					int num =Math.abs(country[nx][ny]-country[i][j]);
					if(num<=R && num>=L) {
						check[nx][ny]=true;
						flag2=true;
						flag=true;
					}
				}
				if(flag2) check[i][j]=true;
			}
		}
	}
	
	private static void change_poupluation(int num) { //인구 이동해주는 함수 
		while(!store.isEmpty()) {
			location peekNum=store.poll();
			int x = peekNum.x; 
			int y = peekNum.y;
			country[x][y]=num; 
		}
	}
	
	private static void bfs(int N , int mx, int my, int L, int R) {
		int count=1;
		int pop_sum=country[mx][my];
		visit[mx][my]=true; 
		store.add(new location(mx,my));
		q.add(new location(mx,my));
		while(!q.isEmpty()) {
			location peekNum=q.poll();
			int x = peekNum.x;
			int y = peekNum.y;
			for(int i=0; i<4;i++) {
				int nx=x+dx[i];
				int ny=y+dy[i];
				if(nx<0 || ny<0 || nx>=N || ny>=N) continue;
				int num = Math.abs(country[nx][ny]-country[x][y]);
				if(visit[nx][ny]!=true && (num>=L && num <=R)) {
					//visit이 안되어있고, 현재 bfs 탐색중인 노드인 country[x][y] 사이와의 국경이 열려있을 때 
					q.add(new location(nx,ny)); // bfs큐에 넣기 
					store.add(new location(nx,ny)); //인구 수 변동 될 큐에 넣기 
					visit[nx][ny]=true;
					count++; //국가 수 
					pop_sum+=country[nx][ny]; //인구 수 
				}
			}

		}
		change_poupluation(pop_sum/count);
	}  
}