[BOJ 16234] 인구 이동

인구 이동

BOJ 16234 : 인구 이동

해설

이 문제는 2차원 배열의 탐색 문제이기 때문에 좌표 형태를 그래프로 바꿔야 한다는 생각을 먼저 하였다.

문제의 입력 예시 4번을 가지고 해설할 것이다.

입력

N : 3, L : 5, R : 10

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

L <= 인구차이(P) <= R

5 <= p <= 10

(x, y) : 나라 - or | : 국경선, # : 인구수

(0, 0 #10) (0, 1 #15) (0, 2 #20)

(1, 0 #20) (1, 1 #30) (1, 2 #25)

(2, 0 #40) (2, 1 #22) (2, 2 #10)

입력 예시를 좌표 형태로 나타내면 위와 같다.

이 상태에서, 인접한 나라들을 탐색하여 국경선을 열 수 있는지 확인해야 한다. 즉, 인접한 두 나라의 인구차이가 L 명 이상 R 명 이하라면 두 나라가 공유하는 국경선을 하루동안 열 수 있다.

인접한 나라를 탐색하기 위해서는 상,하,좌,우 로 탐색하면 된다.

// 상하좌우 : 인접한 나라를 판단하기 위함
private static int[] dx = {-1, 1, 0, 0};
private static int[] dy = {0, 0, 1, -1};

인접한 나라들을 탐색하기 위해서 BFS 방법을 사용하면 된다.

(0, 0) 에 위치한 나라를 시작으로 인접한 나라를 탐색하면 된다.

첫 번째 BFS 탐색 결과 : 첫 번째 연합

(0, 0 #10)-(0, 1 #15)-(0, 2 #20)
  |                       |
(1, 0 #20)-(1, 1 #30)-(1, 2 #25)
                |
           (2, 1 #22)

위 그래프 형태가 첫 번째 연합의 결과이다. 따라서 인구 이동이 1번 일어난다. 인구 이동이 일어난 후에는 연합간의 인구를 균등 분배 해야 하므로 문제에서 주어진 식대로 계산하면 아래와 같다.

• 연합을 이루고 있는 각 칸의 인구수 = 연합의 인구수 / 연합을 이루고 있는 칸의 개수
  • 142(10 + 15 + 20 + 20 + 22 + 25 + 30) / 7 = 20

인구 이동

(0, 0 #20)-(0, 1 #20)-(0, 2 #20)
  |                       |
(1, 0 #20)-(1, 1 #20)-(1, 2 #20)
                |
           (2, 1 #20)

따라서, 연합의 인구수를 계산하기 위한 변수와, 칸의 개수를 나타내는 변수가 필요하다는 것을 알 수 있다. 또한, 연합에 속하는 나라들을 저장하기 위한 자료구조도 필요하다.

BFS 탐색 결과 현재 국경선으로 연결되어 있는 나라들은 방문(Visited) 한 나라들이므로, 다음 BFS 탐색 때 방문 여부를 체크하여 인구 이동이 더 이상 일어나지 않을 때 까지 반복하면 된다.

모든 국경선 닫고, 방문 여부 체크

(0, 0 #20, VISITED) (0, 1 #20 , VISITED) (0, 2 #20 , VISITED)

(1, 0 #20, VISITED) (1, 1 #20 , VISITED) (1, 2 #20 , VISITED)

(2, 0 #40) (2, 1 #20, VISITED) (2, 2 #10)

두 번째 BFS 탐색의 시작은 방문하지 않은 나라 중 가장 빠른 (3, 1) 부터 탐색이 시작될 것이다.

두 번째 연합

             (1, 2 #20)
                 |
(2, 1 #20) - (2, 2 #10)

인구 이동

             (1, 2 #16)
                 |
(2, 1 #16) - (2, 2 #16)

최종 결과 : 더 이상 연합이 불가능하므로 종료

(0, 0 #20) (0, 1 #20) (0, 2 #20)

(1, 0 #20) (1, 1 #20) (1, 2 #16)

(2, 0 #40) (2, 1 #16) (2, 2 #16)

정리

• 2차원 배열의 탐색 문제 -> 그래프
• 입력 값을 배열 형태의 그래프로 표현
• 인접한 나라들을 탐색하기 위해 BFS 알고리즘 이용
• 첫 번째 연합 결과 = 인구 이동
  • 연합의 횟수 = 인구 이동의 횟수
• 연합 > 인구 이동 > 연합한 나라들의 인구 수를 재계산 > 인구 이동이 불가능 할 때 까지 반복

구현

class Country {

    private int x;
    private int y;

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

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }
}

public class Main {

    private static int N;
    private static int L;
    private static int R;
    private static int[][] graph; // (x, y) 나라, 저장된 값은 인구수
    private static boolean[][] visited; // 방문 처리 여부
    private static List<Country> unitedCountries; // 연합된 나라들
    private static int unitedCount = 0; // 연합한 나라의 개수
    private static int sumOfPopulationInUnitedCountry = 0; // 연합한 나라들의 인구수 합
    private static int answer = 0; // 인구 이동이 일어난 횟수

    // 상하좌우 : 인접한 나라를 판단하기 위함
    private static int[] dx = {-1, 1, 0, 0};
    private static int[] dy = {0, 0, 1, -1};

    public static void main(String[] args) {
        input();
        solution();
        System.out.println(answer);
    }

    private static void input() {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        L = sc.nextInt();
        R = sc.nextInt();

        // 그래프, 방문처리여부 초기화
        graph = new int[N][N];

        // 인구수 저장
        for (int i = 0; i < N; i++) {
            for (int k = 0; k < N; k++) {
                graph[i][k] = sc.nextInt();
            }
        }
    }

    // 인구이동이 발생하지 않을 때 까지 반복
    private static void solution() {
        while(true) {
            boolean isMoved = false;
            visited = new boolean[N][N];
            for (int x = 0; x < N; x++) {
                for (int y = 0; y < N; y++) {
                    if(!visited[x][y]) { // uniteByBfs 를 통해 방문처리 된 인접리스트들에 대해서도 생략
                        unite(x, y);
                        if(unitedCountries.size() > 1) {
                            move();
                            answer++;
                            isMoved = true;
                        }
                    }
                }
            }
            if(!isMoved) {
                break;
            }
        }
    }

    private static void unite(int x, int y) {
        Queue<Country> Q = new LinkedList<>();
        unitedCountries = new ArrayList<>();

        Country start = new Country(x, y);
        Q.offer(start);
        unitedCountries.add(start);
        visited[x][y] = true;

        // 연합한 나라의 개수 : 자기 자신으로 초기화
        unitedCount = 1;
        // 연합한 나라의 인구수 합 탐색 대상인 나라의 인구수로 초기화
        sumOfPopulationInUnitedCountry = graph[x][y];
        while(!Q.isEmpty()) {
            Country country = Q.poll();
            x = country.getX();
            y = country.getY();
            int p1 = graph[x][y];
            // 상하좌우 탐색
            for (int i = 0; i < dx.length; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if((nx >= 0 && ny >= 0 && nx < N && ny < N) && !visited[nx][ny]) {
                    int p2 = graph[nx][ny];
                    if(isLinkable(p1, p2)) {
                        Country adjacentCountry = new Country(nx, ny);
                        // 연결 가능한 인접한 나라를 Q 에 넣는다.
                        Q.offer(adjacentCountry);
                        // 연합한 나라를 보관하는 리스트에 넣는다.
                        unitedCountries.add(adjacentCountry);
                        // 연합한 나라의 인구수 합 누적
                        sumOfPopulationInUnitedCountry += p2;
                        // 연합한 나라의 개수 증가
                        unitedCount++;
                        // 방문 처리
                        visited[nx][ny] = true;
                    }
                }
            }
        }
    }

    // 연결 가능한지
    private static boolean isLinkable(int p1, int p2) {
        int absValue = Math.abs(p1 - p2);
        return L <= absValue && absValue <= R;
    }

    // 인구 이동, 연합한 나라들의 인구수를 재계산
    private static void move() {
        for(Country country : unitedCountries) {
            graph[country.getX()][country.getY()] = sumOfPopulationInUnitedCountry / unitedCount;
        }
    }
}