[Java][자바][백준][16234번] 인구이동

문제 설명

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

 

오늘부터 인구 이동이 시작되는 날이다.

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

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

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

입력

첫째 줄에 N, L, R이 주어진다. (1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100)

둘째 줄부터 N개의 줄에 각 나라의 인구수가 주어진다. r행 c열에 주어지는 정수는 A[r][c]의 값이다. (1 ≤ A[r][c] ≤ 100)

인구 이동이 발생하는 횟수가 2,000번 보다 작거나 같은 입력만 주어진다.

출력

인구 이동이 몇 번 발생하는지 첫째 줄에 출력한다.

 

생각

문제에서 하라는 대로 하면 된다.

먼저 각 좌표에서 상하좌우를 살피며 L 이상 R이하인지 확인한다. 만약 범위내에 들어가 있다면, 국경을 열어준다. 나의 경우에는 open[][] 2차원 배열을 만들어서 국경이 열린다면 1로 바꿔주었다. 후에 flag_count라는 국경이 열린 횟수를 증가시켜준다. 만약 flag_count = 0 이라면 중단하고 인구 이동 발생 횟수를 출력해 줄 것이다.

 

후에 bfs / dfs를 통해 open[][]에서 1인 좌표들을 탐색하여 인구를 나눠준다. 후에 각 1인 좌표들에 인구수를 분배해준다. 문제 자체는 크게 어렵지 않다! 하지만 이 문제를 풀어봐야 하는 이유는 이번 11월 역테에서 비슷하지만 좀 더 어려운 문제가 나왔다. 꼭 풀어보길 바란다. (참고로 나는 이 문제를 맞춰서 드디어 A형을 합격했다 ㅎㅎㅎㅎㅎ)

 

자세한 설명을 주석에 적도록 하겠다.

 

KT 최종면접을 준비하느라 블로그에 포스팅을 잘 못했다.. 물론 나중에 1차 2차 면접 후기를 올리겠지만.. 제발 붙었으면 좋겠다. 붙기만 한다면 앞으로의 인생을 겸손하고 감사하게 살아갈탠데.. 제발 붙기를!!!!!!!!!!!!

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
    static int[] dx = {0,0,-1,1};
    static int[] dy = {1,-1,0,0};
    static int N, L, R;
    static int[][] map;
    static boolean[][] visited;
    static int[][] open;
    static int count = 0;
    static int sum = 0;
    static int flag_count = 0;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
        String[] str = br.readLine().split(" ");
        N = Integer.parseInt(str[0]);
        L = Integer.parseInt(str[1]);
        R = Integer.parseInt(str[2]);
        
        map = new int[N][N];
        
        for(int i=0; i<N; i++) {
            str = br.readLine().split(" ");
            for(int j=0; j<N; j++) {
            map[i][j] = Integer.parseInt(str[j]);    
            }
        }
        
        loop: while(true) {
            visited = new boolean[N][N];
            open = new int[N][N];
            flag_count = 0;
            
            for(int i=0; i<N; i++) {
                for(int j=0; j<N; j++) {
                    //각 좌표들에 대해 국경을 열 수 있는지 체크
                    castleOpen(new dot(i,j));
                }
            }
            //연결할 나라가 없다면 break 해준다.
            if(flag_count == 0) {
                break loop;
            } else {
                count++;
            }
            //연결된 나라들에 대해서 인구를 분배해준다.
            for(int i=0; i<N; i++) {
                for(int j=0; j<N; j++) {
                    if(open[i][j] == 1 && !visited[i][j]) {
                        bfs(new dot(i,j));
                    }
                }
            }
            
        }
        
        System.out.println(count);
    }
    
    public static void castleOpen(dot d) {
        int x = d.x;
        int y = d.y;
        
        
        for(int i=0; i<4; i++) {
            int x1 = d.x + dx[i];
            int y1 = d.y + dy[i];
            //L 이상 R이하의 범위이면 두 나라를 연결시켜준다.
            if(x1>=0 && x1<N && y1>=0 && y1<N) {
                if(Math.abs(map[x][y] - map[x1][y1])>=L && Math.abs(map[x][y] - map[x1][y1])<=R) {
                    open[x][y] = 1;
                    open[x1][y1] = 1;
                    flag_count++;
                }
            }
        }
    }
    
    public static void bfs(dot d) {
        Queue<dot> q = new LinkedList<dot>();
        ArrayList<dot> save = new ArrayList<dot>();
        int tmp_count = 0;
        sum = 0;
        visited[d.x][d.y] = true;
        q.add(d);
        //상하좌우에 1이라면 q에 더해준다.
        while(!q.isEmpty()) {
            dot t = q.poll();
            save.add(t);
            int x = t.x;
            int y = t.y;
            sum += map[x][y];
            tmp_count++;
            
            for(int i=0; i<4; i++) {
                int x1 = x + dx[i];
                int y1 = y + dy[i];
                
                if(x1>=0 && x1<N && y1>=0 && y1<N && Math.abs(map[x][y] - map[x1][y1])>=L && Math.abs(map[x][y] - map[x1][y1])<=R && !visited[x1][y1]) {
                    q.add(new dot(x1, y1));
                    visited[x1][y1] = true;
                }
            }
        }
        //나눠줄 인구를 구한 후 큐를 돌며 좌표를 구해 인구를 나누어준다.
        int divide = sum/tmp_count;
        
        for(int i=0; i<save.size(); i++) {
            dot t = save.get(i);
            map[t.x][t.y] = divide;
        }
        
    }
}
 
class dot {
    int x;
    int y;
    
    public dot(int x,int y) {
        this.x= x;
        this.y= y;
    }
}