BOJ16234_인구 이동

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

문제요약

1. 각 칸에는 A[r][c]명이 살고 있다.

2. 인접한 나라 사이에는 국경선이 존재한다.

3. 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.

(1) 국경선을 공유하는 두 나라의 인구 차이가 L~R이라면, 두 나라가 공유하는 국경선을 하루동안 연다.

(2) 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.

(3) 국경선이 열린 각 칸의 인구수는 (국경선이 열린 칸 인구수 총합) / (칸 수)가 된다.

(4) 모든 국경선을 닫는다.

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

문제issue

1. 인구 이동이 없을 때까지 지속해야한다.

2. 인구 이동은 한번에 해야된다.

해결흐름

1. 인구 이동이 없을 때까지 지속해야 되기 때문에 while(true)안에서 실행되도록 한다.

2. 먼저 인구이동이 필요한지 검사한다.

(1) map을 탐색하면서 인접한 곳과의 차이가 L~R이라면 인구이동이 필요한 곳이다.

(2) 그러한 곳이 한곳이라고 존재한다면 flag = true로 해주고 한군데라도 있으면 인구이동이 필요하기 때문에 더 이상 탐색할 필요가 없다.

3. flag = true면 인구이동이 필요하기 때문에 result++해주고 bfs로 인구이동을 실행한다 , 인구이동이 끝난 뒤에는 인구수를 갱신해준다.

flag = false면 더 이상 인구이동이 필요없기 때문에 while(true)를 종료시키고 result를 출력한다.

인구이동

1. map을 탐색하면서 방문했던 곳이 아니면 bfs를 실행하도록 한다.

2. sum은 인접한 칸들의 인구수를 모두 더할 변수 , cnt는 인접한 칸들의 갯수를 카운트 해줄 변수이다.

3. 인접한 곳이 map의 범위안이고 , 방문하지 않았고 , 인구수의 차이가 L~R이라면

(1) q와 q2에 add 해준다. q2는 인구이동이 필요한 곳을 임시저장해주는 큐이다.

(2) 방문체크를 해주고 sum에 더해주고 cnt++ 해준다.

4. sum과 cnt를 이용해서 갱신해줘야 하는 인구수를 구해준다.

5. 인구이동이 필요한 곳을 임시저장 해둔 q2를 q3에 저장해주면서 갱신해줘야 하는 인구수도 같이 add 해준다.

q3는 모든칸에 대한 bfs를 끝내고 마지막에 한번에 인구이동을 해주기 위한 큐이다.

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    
    static class pair{
        int r;
        int c;
        public pair(int r, int c) {
            super();
            this.r = r;
            this.c = c;
        }
    }
    static class pair2{
        int r;
        int c;
        int people;
        public pair2(int r, int c, int people) {
            super();
            this.r = r;
            this.c = c;
            this.people = people;
        }
    }
    
    private static int[] dr = {-1,0,1,0};
    private static int[] dc = {0,1,0,-1};
    private static int[][] map;
    private static boolean[][] visited;
    private static int R;
    private static int L;
    private static int N;
    private static LinkedList<pair2> q3;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine().trim(), " ");
        N = Integer.parseInt(st.nextToken());
        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().trim(), " ");
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        int result = 0;
        while(true) {
            // 인구이동이 필요한지 검사
            boolean flag = false;
            here:for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    for (int k = 0; k < 4; k++) {
                        int nr = i + dr[k];
                        int nc = j + dc[k];
                        if(nr>=0 && nr<N && nc>=0 && nc<N) {
                            if(Math.abs(map[i][j] - map[nr][nc]) >= L && 
                                    Math.abs(map[i][j] - map[nr][nc]) <= R) {
                                // 인구이동이 필요한 곳이 한군데라도 존재한다면 flag 바꾸고 다른 곳 더 살펴볼 필요 없음
                                flag = true;
                                break here;
                            }
                        }
                    }
                }
            }
            
            visited = new boolean[N][N];
            q3 = new LinkedList<pair2>();
            // flag에 따라 bfs 실행할지 안할지
            if(flag) {
                result++;
                for (int i = 0; i < N; i++) {
                    for (int j = 0; j < N; j++) {
                        // 해당하는 칸이 검사했던 칸이 아니면
                        if(!visited[i][j])
                            bfs(i,j);
                    }
                }
                // 인구수 갱신
                while(!q3.isEmpty()) {
                    pair2 p2 = q3.poll();
                    map[p2.r][p2.c] = p2.people;
                }
            }
            else break;
        }
        System.out.println(result);
    } // end of main
 
    private static void bfs(int r, int c) {
        Queue<pair> q = new LinkedList<>();
        // 인구수 갱신이 필요한 부분을 임시 저장해두기 위한 큐
        Queue<pair> q2 = new LinkedList<>();
        q.add(new pair(r,c));
        q2.add(new pair(r,c));
        visited[r][c] = true;
        int sum = map[r][c];
        int cnt = 1;
        
        while(!q.isEmpty()) {
            int q_size = q.size();
            for (int i = 0; i < q_size; i++) {
                pair p = q.poll();
                for (int j = 0; j < 4; j++) {
                    int nr = p.r + dr[j];
                    int nc = p.c + dc[j];
                    if(nr>=0 && nr<N && nc>=0 && nc<N) {
                        if(!visited[nr][nc] && Math.abs(map[p.r][p.c] - map[nr][nc]) >= L && 
                                Math.abs(map[p.r][p.c] - map[nr][nc]) <= R) {
                            q.add(new pair(nr,nc));
                            q2.add(new pair(nr,nc));
                            visited[nr][nc] = true;
                            sum += map[nr][nc];
                            cnt++;
                        }
                    }
                }
            }
        }
        // 인구이동이 필요한 모든 곳 따로 저장 후 한번에 이동
        int number = sum / cnt;
        while(!q2.isEmpty()) {
            pair p = q2.poll();
            q3.add(new pair2(p.r,p.c,number));
        }
    }
} // end of class