백준 16234 - 인구 이동

Java

16234 번 - 인구 이동

문제

N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다.

인구 이동은 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.

• 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루동안 연다.
• 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.
• 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.
• 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.
• 연합을 해체하고, 모든 국경선을 닫는다.

각 나라의 인구수가 주어졌을 때, 인구 이동이 몇 번 발생하는지 구하는 프로그램을 작성하시오.

접근 방법

1. (0,0) ~ (n-1, n-1) 까지 하나씩 탐색
2. bfs를 이용하여 근처에 갈 수 있는 모든 곳 방문
3. 방문 할 때마다 cnt 증가, 총합 증가, 방문했다는 증거 남긴다
4. 방문 했던 곳의 인구를 균등하게 분배
5. 1번 ~ 4번 과정을 while문으로 돌린다 -> 인구 이동이 발생하는 횟수 증가

코드

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

public class Main {
	static int n, L, R, result;
	static int[][] A;
	static boolean[][] vis;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	n = stoi(stk.nextToken());
    	L = stoi(stk.nextToken());
    	R = stoi(stk.nextToken());
    	A = new int[n][n];
    	for(int i = 0; i < n; i++) {
    		stk = new StringTokenizer(br.readLine());
    		for(int j = 0; j < n; j++) {
    			A[i][j] = stoi(stk.nextToken());
    		}
    	}
    	
    	boolean isMoved = false;
    	do {
    		vis = new boolean[n][n];
    		isMoved = false;
    		
    		for(int i = 0; i < n; i++) {
    			for(int j = 0; j < n; j++) {
    				if(!vis[i][j]) {
    					if(!isMoved)
    						isMoved = BFS(i,j);
    					else {
    						BFS(i,j);
    					}
    				}
    			}
    		}
    		
    		if(isMoved) {
    			result++;
    		}
    	}while(isMoved);
    	
    	
    	System.out.println(result);
    	br.close();
	}
	// 우 하 좌 상
	static int[] dy = {0, -1, 0, 1};
	static int[] dx = {1, 0, -1, 0};
	private static boolean BFS(int y, int x) {
		boolean ismoved = false;
		Queue<Pair> q = new LinkedList<>();
		Queue<Pair> saved = new LinkedList<>();
		q.add(new Pair(y,x));
		int sum = 0, cnt = 0, ny, nx;
		Pair p;
		while(!q.isEmpty()) {
			p = q.poll();
			saved.add(p);
			
			for(int i = 0; i < 4; i++) {
				ny = p.y + dy[i];
				nx = p.x + dx[i];
				
				if(isIn(ny,nx,n) && !vis[ny][nx] && CanMove(A[p.y][p.x], A[ny][nx])) {
					q.add(new Pair(ny,nx));
					ismoved = true;
					sum += A[ny][nx];
					vis[ny][nx] = true;
					cnt++;
				}
			}
		}
		
		if(ismoved) { // 한 번이라도 연합 되면
			int rst = sum / cnt;
			while(!saved.isEmpty()) {
				p = saved.poll();
				A[p.y][p.x] = rst; 
			}
		}
		else {	// 연합이 되지 않으면
			vis[y][x] = false;
		}
		
		return ismoved;
	}
	
	public static class Pair{
    	int y;
    	int x;
    	Pair(int k,int v){
    		y = k;
    		x = v;
    	}
		@Override
		public String toString() {
			StringBuilder builder = new StringBuilder();
			builder.append("[").append(y).append(", ").append(x).append("]");
			return builder.toString();
		}	
    }
	// 주어진 범위 안에 있는가
    public static boolean isIn(int y, int x, int size){
        if(y < 0 || y == size || x < 0 || x == size)
            return false;
        return true;
    }
    
    public static boolean CanMove(int A, int B) {
    	int diff = Math.abs(A - B);
    	if(L <= diff && diff <= R) {
    		return true;
    	}
    	return false;
    }
    
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

난이도

⭐⭐⭐★★

후기

if(isIn(ny,nx,n) && !vis[ny][nx] && CanMove(A[p.y][p.x], A[ny][nx])) {
	q.add(new Pair(ny,nx));
	ismoved = true;
	sum += A[ny][nx];
	vis[ny][nx] = true;
	cnt++;
}

BFS는 새로이 갈 수 있는 나라가 만나면,
방문한 인구수의 합, 나라의 수, 방문여부를 if()안에 넣어야한다.
이를 바깥에 넣어서 고생했다.

개선할 점

없