(백준) 16234 인구 이동 - JAVA

16234번: 인구이동

N×N사이즈의 땅이 있고, 땅은 1×1개의 구획으로 나누어져 있다.

각각의 토지에는 나라가 하나씩 존재하고, r행c열에 있는 나라에는 A(r)(c)인이 살고 있다.

인접한 국가 사이에는 국경선이 있습니다.

모

www.acmicpc.net

인기글

알고리즘

NxN 크기의 2차원 배열 탐색, 하나의 정점을 기준으로 탐색하기 위해 DFS사용했다.

사각형에 인접한 국가 중 L ≤ 인구차 ≤R의 나라들끼리의 국경선이 사라져 하나의 연합국이 된다.

4방 탐색(상/하/좌/우)하여 연합국을 확장하고 더 이상 확장할 수 없는 경우 연합국의 인구이동을 수행한다.

✔️주의해야 할 점은 토지 한칸은 하루에 한 번만 탐색가능합니다.

즉, 인구이동이 발생한 토지는 다음날까지 인구이동이 더 이상 발생하지 않는다.

구현 알고리즘

이하의 과정을 더 이상 인구 이동이 일어나지 않을 때까지 반복한다.

(인구이동이 한번이라도 발생한 것을 확인하기 위한 플래그값 isChange 사용)

1. 탐색했는지(인구 이동이 발생했는지) 확인하기 위한 boolean형 2차원 배열의 생성

(1일 동안 이미 한 번 인구 이동이 발생한 경우 더 이상 탐색해야 합니다 x)

2. (아직 탐색하지 않은 토지라면) DFS 탐색을 시작한다.

검색 처리(=방문 처리)
큐에 대응하는 토지의 좌표 정보를 삽입합니다.

(큐: 현재 연합을 이루고 있는 각국의 위치 정보)
현재 연합을 이루고 있는 국가들의 총 인구수를 더한다.
현재 위치(i, j)에서 사방 탐색진행합니다.
if 다음 네비게이션 포인트(ni, nj)가 NxN 크기의 토지 경계를 넘거나 이미 네비게이션한 곳인 경우, 다음 네비게이션 → continue
else 현재 (i, j)와 다음 (ni, nj)의 인구차가 L 이상 R 이하이면 (ni, nj)를 기준으로 DFS 탐색을 반복 (재귀)한다.

3-1. DFS 검색이 끝날 때 대기열 크기가 1이면 대기열을 비우고 다음 지점을 검색합니다.

(큐의 크기가 1 = 탐색을 시작한 나라에서 연합을 이룬 나라가 하나도 없다는 것 = 인구 이동 X)

3-2. 총 인구수/큐의 크기=연합을 이루고 있는 각 구간의 인구수

4. 대기열에 포함 된 연합국의 위치 정보를 취득하고, 연합국의 인구 수를 조정한다.

소스 코드

import java.util.*;
import java.io.*;
/*
 * 특정 땅에서 시작해서 dfs(깊이우선)로 탐색
 * 국경선 열 수 있는 경우, 큐에 넣음 
 * 탐색하다가 더 이상 국경선 열 수 없을 때 큐에 있는 것들 빼서 연합 
 * 큐에 있는 땅들 인구수 조절 
 * 그 다음 탐색 ㄱ */
public class Solution_BaekJoon_16234 {
	private static int dx()= {-1,1,0,0};
	private static int dy()= {0,0,-1,1}; 
	private static int N,L,R;
	private static int()() map;
	private static boolean()() visited;
	private static int sum;
	//하나의 땅에 대한 정보 
	static class Ground{
		//땅 위치(x,y)
		int x;
		int y;
		
		public Ground(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	private static Queue<Ground> que= new LinkedList<>(); 
	
	public static void main(String() args) throws Exception{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st= new StringTokenizer(br.readLine(), " ");
		N= Integer.parseInt(st.nextToken()); //땅의 크기 
		//인구차이가 L명 이상 R명 이하일 때, 국경선 열 수 있음 
		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());
			}
		}
		int count =0; 
		
		while(true) {
		boolean isChange=false; 
		visited= new boolean(N)(N); 
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				if(!
visited(i)(j)) {
					sum=0;
					dfs(i,j); 
					
					// 탐색 시작한 거에서 더 연합 못한 경우 
					if(que.size() == 1) { 
						que.poll(); 
						continue;
					}
                    
					isChange = true;
                    
					//연합국 한 나라 인구수 
					int one_people=sum/que.size(); 
                    //인구 이동 
					while(!
que.isEmpty()) {
						Ground g= que.poll();
						map(g.x)(g.y) = one_people; 
					}
					
				}
			}
		}
			//인구 이동이 한번도 안일어났으면 종료 
			if(!
isChange) break; 
            
			count ++; 
		}
		System.out.println(count);
		
	}//end of main 
	private static void dfs(int i, int j) {
		//방문체크하고, 큐에 넣고, 연합 인구수합에 더하고 
		visited(i)(j) = true;
		que.add(new Ground(i,j)); 
		sum+=map(i)(j); 
		
		for(int d=0; d<4; d++) {
			// 4방탐색 
			int ni = i+dx(d);
			int nj = j+dy(d); 
			//땅 밖으로 나가거나, 이미 탐색 했던 곳 ( 하루에 동시 탐색하는 땅 x ) 
			if(isOut(ni,nj) || visited(ni)(nj)) continue; 
			
			//인접한 두 국가의 인구수 차이
			int dif= Math.abs(map(i)(j)-map(ni)(nj));
			if(dif>=L && dif<=R) {
				dfs(ni, nj); 			
			}
			
		}
	}//end of dfs 
	
	private static boolean isOut(int i, int j) {
		return i<0 || i>=N || j<0 || j>=N;
	}
}//end of class

(백준) 16234 인구 이동 – JAVA

인기글