[G4] 인구이동 : 16234 : Java - BFS, 구현

1.   💎 문제

16234번: 인구 이동

 

 

 

 

 

2. 🤔 어떻게 풀까

이 문제도 퍼져나가는 형식으로 BFS의 전형적인 문제이다. 현재 요소를 기준으로 주위 요소들이 전염되는 방식으로 이전에 풀었던 문제가 들과 유사하다. 단지 이 문제는 전염 조건과 수행해야 하는 로직이 늘었다.

        조건1. 먼저전염 조건은 인접한 칸의 인구수가 L명이상, R명 이하이다.

        조건2. 전염된 나라끼리는 인구수를 다시 계산해야한다.

        조건3. BFS를 한 번만 돌리는 것이 아니라 인구이동이 없을 때까지 실행해야 한다.

위와 같은 조건 3개를 따지면서 BFS 탐색을 진행한다. 

 

 

3. 💡 로직

1. 나라마다 인구 입력

N = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());

        population = new int[N][N];
        isVisited = new boolean[N][N];
        que = new LinkedList<>();
        curQue = new LinkedList<>();

        // 인구수 입력
        for (int i = 0; i < N; i++) {
            population[i] = Arrays.stream(br.readLine().split(" "))
                    .mapToInt(Integer::parseInt)
                    .toArray();
        }

 

 

2. 인구 이동

인구 이동은 더 이상 인구 변화가 없을 때까지 일어난다. 만약 인구 변화가 생기면 `isChage` 플러그를 `true`로 바꿔 탐색을 계속 진행한다. 인구이동은 모든 연합이 동시에 일어난다. 그러므로 인구 이동을 할 모든 연합을 찾는 과정을 1주기라고 하고, 이 때 모든 나라를 돌면서 총 각 연합을 알아내고 인구이동을 시킨다. 동시에 일어난다는 조건이 있지만 각 연합은 다른 연합에 영향을 줄 수 없기에 순차적으로 진행해도 된다.  방문하지 않은 노드를 찾았을 때 새로운 연합이 시작되며, 국경선을 풀 수있는 나라들을 찾는다

 boolean isChage = true;
        int result = 0;
        while (isChage) {
            isChage = false;
            isVisited = new boolean[N][N];
            // 한 주기 시작
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (isVisited[i][j])
                        continue;
                    // 한 연합 시작
                    if(bfs(new Point(i,j))){
                        isChage = true;
                    }
                }
            }
            result++;
        }

 

 

3. 한 연합 찾기

전체적인 과정은 BFS방법이다. 추가로 인구 수를 평균으로 맞춰야 하는 작업을 수행하기 위해 큐에서 요소를 꺼낼 때 `curque` 큐에 해당 요소를 추가한다. 기존 큐는 `poll` 을 하기 때문에 유지할 수 가 없어서 새로운 큐를 만든 것이다.

그 후 큐에서 꺼내 요소의 상하좌우 위치에 있는 나라 들 중, 인접한 칸의 인구수가 L명이상, R명 이하이고, 방문 하지 않은 나라의 찾아 큐에 위치를 삽입한다. 큐가 빌 때까지 작업을 진행하여 이어진 한 연합을 구성하고, 인구수를 평균으로 맞춘다.

 public static boolean bfs(Point start){
        boolean isChage = false;
        // 한 연합 탐색 시작
        int popul_sum = 0;
        que.add(start);
        isVisited[start.x][start.y] = true;

        while (!que.isEmpty()) {
            Point curPoint = que.poll();
            curQue.add(curPoint);
            popul_sum += population[curPoint.x][curPoint.y];

            // 사각지대 비교(차이가 L명이상이고 R명 이하이면 인구이동)
            for (int d = 0; d < 4; d++) {
                Point nextPoint = new Point(curPoint.x + dx[d], curPoint.y + dy[d]);
                if (compare(curPoint, nextPoint) && !isVisited[nextPoint.x][nextPoint.y] ) {
                    que.add(nextPoint);
                    isVisited[nextPoint.x][nextPoint.y] = true;
                    isChage = true;
                }
            }
        }  // 한 연합 탐색 끝

        // 인구 이동
        chagePopulation(popul_sum);
        return isChage;
    }
    
    public static boolean compare(Point p1, Point p2) {
        if (p2.x >= 0 && p2.x < N && p2.y >= 0 && p2.y < N) {
            if ((Math.abs(population[p1.x][p1.y] - population[p2.x][p2.y]) >= L)
                    && Math.abs(population[p1.x][p1.y] - population[p2.x][p2.y]) <= R) {
                return true;
            }
        }
        return false;
    }

 

 

4. 인구수 맞추기

public static void chagePopulation(int sum){
        int avg =  sum/ curQue.size();
        while (!curQue.isEmpty()) {
            Point pos = curQue.poll();
            population[pos.x][pos.y] = avg;
        }
    }

 

 

 

 

4. 📄 전체 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ_인구이동_16234 {

    static BufferedReader br;
    static BufferedWriter bw;
    static int[] dx = new int[]{0, 1, 0, -1};
    static int[] dy = new int[]{1, 0, -1, 0};
    static int[][] population;
    static boolean[][] isVisited;
    static Queue<Point> que;
    static Queue<Point> curQue;
    static int N, L, R;

    public static void main(String[] args) throws Exception {

        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());

        population = new int[N][N];
        isVisited = new boolean[N][N];
        que = new LinkedList<>();
        curQue = new LinkedList<>();

        // 인구수 입력
        for (int i = 0; i < N; i++) {
            population[i] = Arrays.stream(br.readLine().split(" "))
                    .mapToInt(Integer::parseInt)
                    .toArray();
        }

        boolean isChage = true;
        int result = 0;
        while (isChage) {
            isChage = false;
            isVisited = new boolean[N][N];
            // 한 주기 시작
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (isVisited[i][j])
                        continue;
                    // 한 연합 시작
                    if(bfs(new Point(i,j))){
                        isChage = true;
                    }
                }
            }
            result++;
        }
        System.out.println(result-1);

    }
    public static boolean bfs(Point start){
        boolean isChage = false;
        // 한 연합 탐색 시작
        int popul_sum = 0;
        que.add(start);
        isVisited[start.x][start.y] = true;

        while (!que.isEmpty()) {
            Point curPoint = que.poll();
            curQue.add(curPoint);
            popul_sum += population[curPoint.x][curPoint.y];

            // 사각지대 비교(차이가 L명이상이고 R명 이하이면 인구이동)
            for (int d = 0; d < 4; d++) {
                Point nextPoint = new Point(curPoint.x + dx[d], curPoint.y + dy[d]);
                if (compare(curPoint, nextPoint) && !isVisited[nextPoint.x][nextPoint.y] ) {
                    que.add(nextPoint);
                    isVisited[nextPoint.x][nextPoint.y] = true;
                    isChage = true;
                }
            }
        }  // 한 연합 탐색 끝

        // 인구 이동
        chagePopulation(popul_sum);
        return isChage;
    }

    public static void chagePopulation(int sum){
        int avg =  sum/ curQue.size();
        while (!curQue.isEmpty()) {
            Point pos = curQue.poll();
            population[pos.x][pos.y] = avg;
        }
    }

    public static boolean compare(Point p1, Point p2) {
        if (p2.x >= 0 && p2.x < N && p2.y >= 0 && p2.y < N) {
            if ((Math.abs(population[p1.x][p1.y] - population[p2.x][p2.y]) >= L)
                    && Math.abs(population[p1.x][p1.y] - population[p2.x][p2.y]) <= R) {
                return true;
            }
        }
        return false;
    }
}

class Point {
    int x;
    int y;

    Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}