[백준] 인구 이동 - 16234번

문제설명

https://www.acmicpc.net/problem/16234

16234번: 인구 이동

 

 

 

기본아이디어

시뮬레이션 문제입니다. 나라 갯수가 작기 때문에 BFS 탐색을 통해서 인구 이동이 발생하는 나라 그룹을 만들고 인구이동 시키고 다시 그룹을 만들고 이런 방식으로 구현했습니다.

 

 

구현코드

 

public static void main(String[] args) throws IOException {
        st = new StringTokenizer(input.readLine());
        N = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());
 
        A = new int[N][N];
        for(int i = 0; i < N; i++){
            int[] temp = new int[N];
            st = new StringTokenizer(input.readLine());
            for(int j = 0; j < N; j++){
                temp[j] = Integer.parseInt(st.nextToken());
            }
            A[i] = temp;
        }
        System.out.println(move());
    }
    static int N, L, R;
    static int[][] A;
    static boolean[][] isVisited;
    static int move(){
        int ans = -1;
        boolean flag = true;
        while(flag){
            flag = false;
            isVisited = new boolean[N][N];
            for(int i = 0; i < N; i++){
                for(int j = 0; j < N; j++){
                    if(!isVisited[i][j]){
                        isVisited[i][j] = true;
                        if(bfs(i, j)){
                            flag = true;
                        }
                    }
                }
            }
            ans++;
        }
        return ans;
    }
 
    static int[] dr = {1, -1, 0, 0};
    static int[] dc = {0, 0, 1, -1};
    static boolean bfs(int r, int c){
        Queue<int[]> queue = new LinkedList<>();
        List<int[]> list = new ArrayList<>();
        queue.add(new int[]{r,c});
        list.add(new int[]{r,c});
        int sum = A[r][c];
        int count = 1;
        while(!queue.isEmpty()){
            int[] loc = queue.poll();
            for(int d = 0; d < 4; d++){
                int nr = loc[0] + dr[d];
                int nc = loc[1] + dc[d];
                if(isIn(nr, nc) && !isVisited[nr][nc]){
                    int diff = Math.abs(A[nr][nc] - A[loc[0]][loc[1]]);
                    if(diff >= L && diff <= R){
                        isVisited[nr][nc] = true;
                        queue.add(new int[]{nr,nc});
                        list.add(new int[]{nr,nc});
                        sum += A[nr][nc];
                        count++;
                    }
                }
            }
        }
        if(count == 1){
            return false;
        }
        int population = sum / count;
        for(int[] loc : list){
            A[loc[0]][loc[1]] = population;
        }
        return true;
    }
    static boolean isIn(int r, int c){
        return r >= 0 && r < N && c >= 0 && c < N;
    }
 

 

정리, 기억할 내용

1. 시뮬레이션 문제는 동작을 함수로 나누고, 각 함수가 제대로 실행되는지 테스트 하자

2. BFS 탐색에서는 방문체크를 어떻게 할 지 고민하자.