[백준 P16234] 인구 이동 Java

P16234 인구 이동

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]의 값이다. (0 ≤ A[r][c] ≤ 100)

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

2 20 50
50 30
20 40

2 40 50
50 30
20 40

2 20 50
50 30
30 40

3 5 10
10 15 20
20 30 25
40 22 10

4 10 50
10 100 20 90
80 100 60 70
70 20 30 40
50 20 100 10

출력값

인구 이동이 며칠 동안 발생하는지 첫째 줄에 출력한다.

1

0

1

2

3

알고리즘

전형적인 구현 문제이다. 문제는 다음과 같은 순서로 풀었다.

1. 특정 국가에서 인접국과 인원수를 비교하여 국경을 개방할 방향을 선정한다. 
2. 0 위 / 1 왼쪽 / 2 아래 / 3 오른쪽 으로 비트 마스킹을 이용하여 기록한다, 각 자리 수를 2의 지수승 하여 나타낸다.  2 ^ 방향 인덱스
	- 위 1 / 왼쪽 2 / 아래 4 / 오른쪽 8
	- 만약 위와 왼쪽이 개방되었다면 3이 기록된다.
3. 개방할 국경을 기록한 뒤에, 실제 이동 한다.
4. 모든 국가를 순회하면서 bfs를 돌고 국경 개방이 결정난 그룹을 순회하면서 총합과 평균을 구한다.
5. 그 국가를 다시 순회하면서 내부의 인원수를 수정한다.
6. 국가의 인원 정보가 변경되었으므로 개방 정보는 다시 업데이트 되어야 한다.

특정 국가에서 인접국과 인원수를 비교하여 개방이 가능한 국가와 방향을 선정한다. movable() 메서드의 return 값이 true라면 개방이 가능한 국경이 존재하는 것으로 봤다.

비트 마스킹을 사용하여 개방된 국경의 방향을 저장한 점이 특별하다. 각 방향은 위:0, 왼:1, 아래:2, 오:3을 나타내고 1의 비트 시프트 (<<) 연산을 각 방향이 나타내는 수 만큼 진행한다. 그렇게 각 방향은 다음의 숫자로 저장된다.

 

위 : 1 << 0 = 1

왼 : 1 << 1 = 2

아래 : 1 << 2 = 4

오 : 1 << 3 = 8

 

그러고 개방된 방향은 그 수를 더해준다. 즉 위와 왼쪽이 개방되었다면 1 + 2 = 3이 기록된다.

public static boolean movable() {
    boolean isAble = false;
    for (int r = 0; r < N; r++) {
        for (int c = 0; c < N; c++) {
            //각 칸을 모두 4방탐색 -> 갈 수 있는지 판단
            int current = map[r][c];
            int flag = 0;

            for (int i = 0; i < 4; i++) {
                int newR = r + dr[i];
                int newC = c + dc[i];

                if (0 <= newR && newR < N && 0 <= newC && newC < N) {
                    int neigh = map[newR][newC];
                    int diff = Math.abs(neigh - current);
                    if (L <= diff && diff <= R) {
                        // 이동할 수 있도록 열어둠
                        flag = flag | 1 << i;
                        isAble = true;
                    }
                }
            }
            move[r][c] = flag;
        }
    }
    return isAble;
}

개방할 국경을 선정한 뒤에 실제로 이동한다. 이동하는 코드는 다음과 같다. 모든 국가를 순회하면서 인원의 총합과 평균을 구한다. 이 과정을 통해 국경을 개방한 나라의 인원수가 어떻게 되는지 구하고, 국경이 개방된 곳의 좌표를 순회하면서 내부 인원수를 변경한다. 국경이 더 이상 개방될 수 없을 때 까지 이를 반복한다.

public static void bfs(int r, int c) {
    Queue<Integer[]> q = new LinkedList<>();
    Queue<Integer[]> movingQ = new LinkedList<>();

    visited[r][c] = true;
    int total = map[r][c];
    int countryCnt = 1;

    q.add(new Integer[] {r, c});
    movingQ.add(new Integer[] {r, c});

    // 총합을 우선 구함
    while (!q.isEmpty()) {

        Integer[] current = q.poll();
        int curR = current[0];
        int curC = current[1];

        for (int i = 0; i < 4; i++) {
            int newR = curR + dr[i];
            int newC = curC + dc[i];

            if (0 <= newR && newR < N && 0 <= newC && newC < N) {
                // 갈 수 있고, 아직 안 갔으면
                if (!visited[newR][newC] && (move[curR][curC] & (1 << i)) != 0) {
                    visited[newR][newC] = true;
                    total += map[newR][newC];
                    countryCnt++;

                    q.add(new Integer[] {newR, newC});
                    movingQ.add(new Integer[] {newR, newC});
                }
            }
        }
    }

    // 실제로 이동을 함
    int targetPeople = (int) Math.floor(total / countryCnt);
    while (! movingQ.isEmpty()) {
        Integer[] current = movingQ.poll();
        map[current[0]][current[1]] = targetPeople;
    }
}

 

전체 코드는 아래와 같다.

 

코드

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

public class Main {
    static final int[] dr = {-1, 0, 1, 0};
    static final int[] dc = {0, -1, 0, 1};

    static int N, L, R;
    static int[][] map;
    static int[][] move;
    static boolean[][] visited;
    static int answer;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        map = new int[N][N];
        move = new int[N][N];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        while (movable()) {
            // 이동을 함
            visited = new boolean[N][N];
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (visited[i][j] == false) bfs(i, j);
                }
            }

            // 초기화
            for (int i = 0; i < N; i++) Arrays.fill(move[i], 0);
            answer++;
        }

        System.out.println(answer);
    }

    public static boolean movable() {
        boolean isAble = false;
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                //각 칸을 모두 4방탐색 -> 갈 수 있는지 판단
                int current = map[r][c];
                int flag = 0;

                for (int i = 0; i < 4; i++) {
                    int newR = r + dr[i];
                    int newC = c + dc[i];

                    if (0 <= newR && newR < N && 0 <= newC && newC < N) {
                        int neigh = map[newR][newC];
                        int diff = Math.abs(neigh - current);
                        if (L <= diff && diff <= R) {
                            // 이동할 수 있도록 열어둠
                            flag = flag | 1 << i;
                            isAble = true;
                        }
                    }
                }
                move[r][c] = flag;
            }
        }
        return isAble;
    }

    public static void bfs(int r, int c) {
        Queue<Integer[]> q = new LinkedList<>();
        Queue<Integer[]> movingQ = new LinkedList<>();

        visited[r][c] = true;
        int total = map[r][c];
        int countryCnt = 1;

        q.add(new Integer[] {r, c});
        movingQ.add(new Integer[] {r, c});

        // 총합을 우선 구함
        while (!q.isEmpty()) {

            Integer[] current = q.poll();
            int curR = current[0];
            int curC = current[1];

            for (int i = 0; i < 4; i++) {
                int newR = curR + dr[i];
                int newC = curC + dc[i];

                if (0 <= newR && newR < N && 0 <= newC && newC < N) {
                    // 갈 수 있고, 아직 안 갔으면
                    if (!visited[newR][newC] && (move[curR][curC] & (1 << i)) != 0) {
                        visited[newR][newC] = true;
                        total += map[newR][newC];
                        countryCnt++;

                        q.add(new Integer[] {newR, newC});
                        movingQ.add(new Integer[] {newR, newC});
                    }
                }
            }
        }

        // 실제로 이동을 함
        int targetPeople = (int) Math.floor(total / countryCnt);
        while (! movingQ.isEmpty()) {
            Integer[] current = movingQ.poll();
            map[current[0]][current[1]] = targetPeople;
        }
    }
}