[백준] 인구 이동 - 자바(Java)

문제 링크

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

문제 설명

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

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

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

• 국경선을 공유하는 두 나라의 인구 차이가 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번 보다 작거나 같은 입력만 주어진다.

 

문제 풀이

[고려사항]

배열 크기는 최대가 50x50 이고, 인구 이동이 발생하는 일수는 최대 2,000번이다. 

모든 배열을 매번 접근한다고 가정했을때, 최대 50 x 50 x 2000 = 5,000,000 (5백만)번의 접근이 있을 수 있다.

* 시간 제한 2초면 자바는 ×2+1 초라서 5초내에 완료해야한다. 그리고 초당 10^7~10^8회 연산을 수행할 수 있다고 가정했을때, 최대 접근 수가 이보다 적기 때문에 정답을 위해 크게 고려하지는 않아도 될 듯 하다. 물론 아예 생각안해도 된다는건 아니지만.

[알고리즘, 구현방법]

인접 국가를 방문하면서 인구 수 차이 조건에 따라 국경선 개방 여부를 결정할 수 있으므로,  BFS 알고리즘을 사용해서 확인했다.

 

국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면 연합국이 되는데, 연합국은 하루에 여러개가 나올 수 있다.

그래서 연합국을 찾아 인구 이동하는 기준을 하루로 두고, 인접 국가를 탐색하는 방식으로 구현했다.

 

연합국을 찾아 인구 이동하는 함수인 movePeople을 반복해서, movePeople이 성공하는 경우, 인구 이동 일자를 +1 했다.

인구 이동의 성공 여부(availableFlag)는 movePeople 함수내에서 한번이라도 연합국이 만들어지면 true로 세팅하여 반환하였다.

 

인구 이동 함수(movePeople)에서는 인접 국가를 방문하면서 조건에 부합하면 연합국으로 묶어서 (연합국 인구 수 / 연합국 개수)명을 재분배하여 인구 이동을 구현했다. (BFS 알고리즘 사용)

 

상세 사항은 정답 코드의 주석을 따라가면 된다.

정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int[][] earth;
    static int n, l, r;
    public static void main(String[] args) throws IOException {
        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());

        // 인구수 입력
        earth = new int[n][n];
        for (int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j=0; j<n; j++) {
                earth[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 인구 이동
        int day = 0;
        while (true) {
            if (!movePeople()) break; // 인구 이동이 실패한 경우 반복문 종료
            day++; // 인구 이동 성공한 경우 일 수 증가
        }
        System.out.println(day);
    }

    public static boolean movePeople() {
        int[] dx = {0,1,0,-1};
        int[] dy = {1,0,-1,0};
        boolean[][] visited = new boolean[n][n];
        Queue<Pointer> q = new LinkedList<>();
        boolean availableFlag = false;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (!visited[i][j]) { // 방문하지 않은 땅인 경우
                    q.offer(new Pointer(i, j)); // BFS Queue에 삽입
                    visited[i][j] = true;

                    // BFS Queue에 저장되어 아래 while문을 타면 하나의 연합국으로 계산
                    List<Pointer> pointers = new ArrayList<>(); // 하나의 연합국 정보를 담을 Pointer 리스트
                    int sum = earth[i][j]; // 연합의 인구수
                    int cnt = 1; // 연합을 이루고 있는 칸의 개수

                    while (!q.isEmpty()) {
                        Pointer nowPointer = q.poll();
                        pointers.add(nowPointer);

                        for (int k = 0; k < 4; k++) { // 4방향 탐색
                            int nx = nowPointer.x + dx[k];
                            int ny = nowPointer.y + dy[k];

                            if (nx >= 0 && nx < n && ny >= 0 && ny < n) { // 범위 체크
                                if (!visited[nx][ny]) { // 방문하지 않은 인접 땅인 경우
                                    int diff = Math.abs(earth[nowPointer.x][nowPointer.y] - earth[nx][ny]); // 현재 땅과 인접땅의 인구 차이 계산
                                    if (diff >= l && diff <= r) { // L명 이상 R명 이하인 경우 국경선 열림
                                        visited[nx][ny] = true; // 인접 땅 방문 표시

                                        // 연합국 처리
                                        sum += earth[nx][ny]; // 연합국 인구 수 누적
                                        cnt++; // 연합국 개수 증가

                                        q.add(new Pointer(nx, ny));
                                        pointers.add(new Pointer(nx, ny)); // 현재 연합국에 추가
                                    }
                                }
                            }
                        }
                    }
                    // 인구 이동을 할 수 없는 경우, 다음 땅에서 인접국 확인
                    if (pointers.size() == 1) continue;

                    // 현 연합국 인구 이동
                    int people = sum / cnt; // 연합에 분배될 인구 수
                    for (Pointer p : pointers) {
                        earth[p.x][p.y] = people;
                    }
                    availableFlag = true; // 인구 이동이 한번이라도 있다면 true 반환
                }
            }
        }
        return availableFlag;
    }

    public static class Pointer{
        int x;
        int y;
        public Pointer(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}