[BOJ/백준] 16234 - 인구이동 (Java,G4)

BOJ 16234 인구이동

16234번: 인구 이동

카테고리

구현, 시뮬레이션, 그래프 탐색, 너비 우선 탐색

시간복잡도

O(N)

해설

구현문제답게, 주어진 조건을 빠짐없이 작성하면 되는 문제입니다.
이 문제에서는 2가지 '어떻게 연합을 이루는가'와 '인구 이동 후의 인구수 관리'를 신경 써서 작성하면 큰 어려움은 없는 문제입니다.

문제 조건

 

 

1 이상 50 이하의 N이 주어지고, 2차원 배열의 형태로 주어지기 때문에 최대 50*50개의 국가가 존재합니다. 그리고 인구 이동은 최대 2,000번까지 발생한다는 것을 기억하고, 문제를 접근하겠습니다.

 

문제 접근

 

위 조건을 읽고 '어떻게 연합을 이루는가'와 '인구 이동 후의 인구수 관리'를 어떤 식으로 해결할 지에 대해서 생각해 보았고, 다음과 같이 접근하려고 했습니다.

 

1. 어떻게 연합을 이루는가

먼저 주어진 조건에 따라서 알 수 있는 정보는 이렇습니다.

• 인접한 국가는 해당 국가(r,c) 기준으로 4방향에 있는 국가이다.
• 연합을 이룰 수 있는 조건은  L <= | 현재 국가의 인구수 - 인접 국가의 인구수| <= R을 만족해야 한다.

이 두 가지 정보를 통해 연합을 이루기 위해서는, 인접한 국가를 구하는 방법으로는 현재 위치를 기준으로 상, 하, 좌, 우의 좌표가 유효한지 ( 0 <= r < n && 0 <= c < n)   체크 후, 연합을 이룰 수 있는 조건을 충족시킨다면, 연합에 추가하고, 이후엔 추가한 국가들의 상, 하, 좌, 우의 국가들에 대해서 체크를 하는 식으로 접근하려고 했습니다.

이 정보를 통해, 너비우선탐색을 이용하면, 쉽게 연합을 이룰 수 있는지 체크할 수 있다고 생각했습니다.

 

2. 인구 이동 후의 인구수 관리를 어떻게 할 것인가?

연합을 이루고 나서, 인구가 이동하게 되면, 연합에 속한 국가들은 인구수가 변하게 됩니다. 이 시점에서 바로 인구를 변경하게 된다면, 다음 연합을 이룰 때, 영향을 줄 수 있습니다.

그렇기 때문에, 영향을 주지 않는 방법을 생각해보아야 합니다.

저는 처음에 인구 이동을, 모든 연합을 맺은 이후에 진행하면 되겠다고 생각을 했습니다. 하지만 문제를 풀고 나서 다시 생각해 보니, BFS를 진행할 때 사용하는 visited 배열을 이용한다면, 이미 연합을 이룬 국가는 방문하지 않아서 즉시 인구 이동을 진행해도 큰 문제는 없었습니다.

 

문제 풀이

사용 변수

static int days; // 인구 이동이 발생한 일수
static int[][] matrix; // 전체 국가의 인구수 정보
static int n, l, r;   // 판의 크기, 연합 형성 가능 최소 인원차, 연합 형성 가능 최대 인원 차
static int[][] deltas = { // 상,하,좌,우 좌표값
        {-1,0},{1,0},{0,-1},{0,1}
};
static boolean [][] visited; // bfs에서 이용하는 방문배열
static Queue<Country> unions;  // 연합들을 관리하는 큐
static Queue<Country> innerQueue; // bfs에서 사용할 큐

// 국가의 정보를 가지고있는 노드들로 LinkedList를 구현
static class Country{
    int r;
    int c;
    int nOfChains; // LinkedList의 Size 
    int nOfPeople; // 연합의 총 인원수

    Country next; // 다음 노드

    public Country(int r, int c, Country next) {
        this.r = r;
        this.c = c;
        this.next = next;
    }
}

문제를 해결하기 위해서 위와 같은 변수들을 이용하였습니다. 저는 '2. 인구 이동 후의 인구수 관리를 어떻게 할 것인가?'에서 모든 연합 형성이 끝난 후, 인구 이동을 진행하려 했습니다. 그래서 각 bfs가 끝날 때 Country(연결리스트)를 반환하고, 이를 Queue(unions)에 저장을 해서, 모든 연합 형성이 끝났을 때, 다시 꺼내면서 인구 이동을 진행하려고 했습니다.

 

 

전체 로직

private static void move() {
    while (true) {
        createUnion();
        if(unions.isEmpty()) break;
        rebuildMatrix();
        days++;
    }
}

인구 이동 문제에서 동작하는 전체 로직은 위와 같습니다. 연합을 형성합니다. 이때 형성되는 연합이 없다면 로직이 종료됩니다. 연합을 형성했다면, 인구 이동이 발생합니다(rebuildMatrix). 이 과정이 끝나면 인구 이동이 발생한 일수(days)가 1증가하고, 전체 로직을 반복합니다.

 

 

연합 형성

private static void createUnion() {
    visited = new boolean[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if(visited[i][j]) continue;
            Country union = bfs(i, j);
            if (union.nOfChains > 1) {
                unions.add(union);
            }
        }
    }
}

연합을 형성하는 로직입니다. 전체 2차원 배열을 기준으로 bfs를 돌아야 하기 때문에, 방문 배열을 초기화해주고, bfs를 통해 연합을 형성합니다. 연합을 이루고 있는 국가의 수가 1 이하일 때(연합 형성 X)가 아니라면, 연합을 다루는 queue에 해당 연합을 추가합니다.

 

너비우선탐색

private static Country bfs(int r, int c){
    int chains = 0; // 연결 리스트의 사이즈 
    int nOfPeople = 0; // 연합의 전체 인구 수
    Country head = new Country(r, c, null); 
    visited[r][c] = true;
    innerQueue.add(head);
    while (!innerQueue.isEmpty()) {
        Country poll = innerQueue.poll();
        chains++; // 사이즈를 증가시킨다.
        nOfPeople += matrix[poll.r][poll.c]; // 인구 수를 추가한다.
        for (int[] del : deltas) { // 상,하,좌,우 좌표를 체크
            int nr = poll.r + del[0];
            int nc = poll.c + del[1];
// 상,하,좌,우 좌표의 값이 2차원 배열의 범위 내에 있는지, 아직 방문하지 않았는지, 연합을 형성할 수 있는지를 체크
            if (isIn(nr, nc) && !visited[nr][nc] && canUnion(matrix[poll.r][poll.c], matrix[nr][nc])) { 
                visited[nr][nc] = true;
// 현재 head가 새로운 country의 next가 되고, 새로운 country가 head가 되면서 연결리스트를 형성한다.
                head = new Country(nr,nc,head);
                innerQueue.add(head);
            }
        }
    }
    head.nOfChains = chains;
    head.nOfPeople = nOfPeople;
    return head;
}

BFS를 돌면서 연합에 필요한 정보(연합을 구성하는 국가의 수, 연합의 총 인구수)를 기록하면서, 연합을 형성합니다. 이때 BFS를 위한 조건(다음 탐색 범위가 2차원 배열 내에 있는지, 아직 방문하지 않은 배열인지)과 연합을 형성할 수 있는지를 체크하면서 탐색을 진행하고, 모든 탐색이 끝나면, 연결리스트를 반환합니다.

 

BFS를 위한 조건 체크 메서드

private static boolean canUnion(int from, int to) {
    int diff = Math.abs(from - to);
    return diff >= l && diff <= r;
}

private static boolean isIn(int row, int col) {
    return row >= 0 && row < n && col >= 0 && col < n;
}

isIn 메서드는 다음 탐색의 범위가 2차원 배열 내에 있는지, canUnion 메서드는 연합 형성 조건인 l <= |현재 국가의 인구수 - 다음 국가의 인구수| <= r 을 만족하는지를 체크합니다.

 

인구 이동

private static void rebuildMatrix(){
    while (!unions.isEmpty()) {
        Country union = unions.poll();
        int avg = calcAvgPopulation(union.nOfPeople, union.nOfChains);
        while (union != null) {
            matrix[union.r][union.c] = avg;
            union = union.next;
        }
    }
}
private static int calcAvgPopulation(int nOfPeoples, int nOfChains) {
    return nOfPeoples / nOfChains;
}

모든 국가들에 대해서 연합 형성이 끝나면, 인구 이동이 발생합니다. 인구 이동이 발생하면 연합에 속한 모든 국가들의 인구수는 연합의 평균 인구수로 변합니다.

 

 

전체 코드

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


/*
    필요한 것
    r*c matrix
    L,R 변수
    delta 배열
    각 bfs에서의 결과를 담을 자료구조
    각 나라를 저장할 자료구조
    visited 배열
    날짜가 얼마나 지났는지 변수

    1 <= N <= 50, 1 <= L <= R <= 100
    모든 인구수는 0 ~ 100

    예상 시간복잡도 O(N^2)

    작동 로직
    0. 날짜를 +1 해준다.
    1. 전체 matrix에 대해서 bfs를 진행해서 연합을 만든다.
    1-1 연합의 개수가 0개라면 종료한다.
    2. 연합별로 matrix의 값을 변경한다.
    1,2가 반복한다.
 */
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int days;
    static int[][] matrix;
    static int n, l, r;
    static int[][] deltas = {
            {-1,0},{1,0},{0,-1},{0,1}
    };
    static boolean [][] visited;
    static Queue<Country> unions;
    static Queue<Country> innerQueue;


    public static void main(String[] args) throws Exception {
        setVariables();
        move();
        System.out.println(days);

    }

    private static void move() {
        while (true) {
            createUnion();
            if(unions.isEmpty()) break;
            rebuildMatrix();
            days++;
        }
    }

    private static void log(){
        for (int[] ints : matrix) {
            System.out.println(Arrays.toString(ints));
        }
        System.out.println();
    }

    private static void rebuildMatrix(){
        while (!unions.isEmpty()) {
            Country union = unions.poll();
            int avg = calcAvgPopulation(union.nOfPeople, union.nOfChains);
            while (union != null) {
                matrix[union.r][union.c] = avg;
                union = union.next;
            }
        }
    }

    private static int calcAvgPopulation(int nOfPeoples, int nOfChains) {
        return nOfPeoples / nOfChains;
    }

    private static void createUnion() {
        visited = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(visited[i][j]) continue;
                Country union = bfs(i, j);
                if (union.nOfChains > 1) {
                    unions.add(union);
                }
            }
        }
    }

    private static Country bfs(int r, int c){
        int chains = 0; // 연결 리스트의 사이즈
        int nOfPeople = 0; // 연합의 전체 인구 수
        Country head = new Country(r, c, null);
        visited[r][c] = true;
        innerQueue.add(head);
        while (!innerQueue.isEmpty()) {
            Country poll = innerQueue.poll();
            chains++; // 사이즈를 증가시킨다.
            nOfPeople += matrix[poll.r][poll.c]; // 인구 수를 추가한다.
            for (int[] del : deltas) { // 상,하,좌,우 좌표를 체크
                int nr = poll.r + del[0];
                int nc = poll.c + del[1];
                // 상,하,좌,우 좌표의 값이 2차원 배열의 범위 내에 있는지, 아직 방문하지 않았는지, 연합을 형성할 수 있는지를 체크
                if (isIn(nr, nc) && !visited[nr][nc] && canUnion(matrix[poll.r][poll.c], matrix[nr][nc])) {
                    visited[nr][nc] = true;
                    // 현재 head가 새로운 country의 next가 되고, 새로운 country가 head가 되면서 연결리스트를 형성한다.
                    head = new Country(nr,nc,head);
                    innerQueue.add(head);
                }
            }
        }
        head.nOfChains = chains;
        head.nOfPeople = nOfPeople;
        return head;
    }



    private static void setVariables() throws IOException {
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        l = Integer.parseInt(st.nextToken());
        r = Integer.parseInt(st.nextToken());

        matrix = new int[n][n];
        visited = new boolean[n][n];
        unions = new ArrayDeque<>();
        innerQueue = new ArrayDeque<>();

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

    private static boolean canUnion(int from, int to) {
        int diff = Math.abs(from - to);
        return diff >= l && diff <= r;
    }

    private static boolean isIn(int row, int col) {
        return row >= 0 && row < n && col >= 0 && col < n;
    }


    // 국가의 정보를 가지고있는 노드들로 LinkedList를 구현
    static class Country{
        int r;
        int c;
        int nOfChains; // LinkedList의 Size
        int nOfPeople; // 연합의 총 인원수

        Country next; // 다음 노드

        public Country(int r, int c, Country next) {
            this.r = r;
            this.c = c;
            this.next = next;
        }
    }






}

 

결과