[JAVA] BOJ 백준 16234번 - 인구 이동

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

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

---

2. 내가 푼 방법

처음에 같은 연합임을 확인하는 과정을 List<List<Tuple>> 처럼 리스트 안에 Object 리스트를 선언한 변수에다가 저장시켜 두고 확인했다. 하지만 다른 분들과 실행 속도 측면에서 현저히 떨어져서 union find 알고리즘을 이용해 개선했다.

 

bfs 함수에서 개방일을 카운팅해주고, isOpen 함수에서 연합이 생성된다면 true를 반환해 주는 코드를 작성했다.

public static int bfs () {
    int dateCnt = 0;

    while (isOpen()) {
        dateCnt++;
    }

    return dateCnt;
}

 

위에서 언급했던 union-find 알고리즘은 isOpen 함수에서 사용됐다.

같은 연합인지 확인하는 parent 변수, 각 연합들의 인구 수와 나라 수를 카운팅 해주는 sum 변수를 각각 선언해주었다.

checkCountry 함수에서 동일한 연합끼리 묶어주면, 그 이후에 0부터 N*N까지 인구수, 나라 수 카운팅해주고 동일한 연합끼리 인구수를 나누는 작업을 거친다.

public static boolean isOpen () {
    boolean open = false;

    int[][] sum = new int[2][N*N]; // [0]행에는 같은 연합 인구수, [1]행에는 같은 연합 나라수
    int[] parent = new int[N*N]; // 같은 연합
    initParent(parent);

    boolean[][] check = new boolean[N][N];

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (!check[i][j]) {
                checkCountry(i, j, check, parent);
            }
        }
    }

    // 인구수, 나라수 카운팅
    for (int i = 0; i < N*N; i++) {
        int p = find(parent, i);
        sum[0][p] += arr[i/N][i%N];
        sum[1][p]++;
    }

    // 같은 연합끼리 인구수 나눔
    for (int i = 0; i < N*N; i++) {
        int p = find(parent, i);

        int calculate = (int) (sum[0][p] / sum[1][p]);

        if (calculate != arr[i/N][i%N]) open = true;
        arr[i/N][i%N] = calculate;
    }

    return open;
}

---

3. 자바 코드

깃허브 풀이 주소

https://github.com/geujeog/BOJ/blob/main/B16234.java

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

class Main {
    static int N;
    static int L;
    static int R;
    static int[][] arr;

    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter 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());
        arr = new int[N][N];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < N; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        bw.write(bfs()+"");

        br.close();
        bw.flush();
        bw.close();
    }

    public static int bfs () {
        int dateCnt = 0;

        while (isOpen()) {
            dateCnt++;
        }

        return dateCnt;
    }

    public static boolean isOpen () {
        boolean open = false;

        int[][] sum = new int[2][N*N]; // [0]행에는 같은 연합 인구수, [1]행에는 같은 연합 나라수
        int[] parent = new int[N*N]; // 같은 연합
        initParent(parent);

        boolean[][] check = new boolean[N][N];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (!check[i][j]) {
                    checkCountry(i, j, check, parent);
                }
            }
        }

        // 인구수, 나라수 카운팅
        for (int i = 0; i < N*N; i++) {
            int p = find(parent, i);
            sum[0][p] += arr[i/N][i%N];
            sum[1][p]++;
        }

        // 같은 연합끼리 인구수 나눔
        for (int i = 0; i < N*N; i++) {
            int p = find(parent, i);

            int calculate = (int) (sum[0][p] / sum[1][p]);

            if (calculate != arr[i/N][i%N]) open = true;
            arr[i/N][i%N] = calculate;
        }

        return open;
    }

    public static void checkCountry (int i, int j, boolean[][] check, int[] parent) {
        Queue<Tuple> queue = new LinkedList<>();
        queue.add(new Tuple(i, j, 0));

        while (!queue.isEmpty()) {
            Tuple tuple = queue.poll();
            int x = tuple.x;
            int y = tuple.y;
            int beforePopulation = tuple.population;

            if (x < 0 || y < 0 || x >= N || y >= N) continue;
            if (check[x][y]) continue;

            if (beforePopulation != 0) {
                int diff = Math.abs(beforePopulation - arr[x][y]);

                if (diff >= L && diff <= R) {
                    union(parent, i*N+j, x*N+y);
                }
                else continue;
            }

            check[x][y] = true;

            queue.add(new Tuple(x-1, y, arr[x][y]));
            queue.add(new Tuple(x+1, y, arr[x][y]));
            queue.add(new Tuple(x, y-1, arr[x][y]));
            queue.add(new Tuple(x, y+1, arr[x][y]));
        }
    }

    public static class Tuple {
        int x;
        int y;
        int population;

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

    public static void initParent (int[] parent) {
        for (int i = 0; i < N*N; i++) {
            parent[i] = i;
        }
    }

    public static int find (int[] parent, int x) {
        if (parent[x] == x) return x;

        return find(parent, parent[x]);
    }

    public static void union (int[] parent, int x, int y) {
        x = find(parent, x);
        y = find(parent, y);

        if (x < y) {
            parent[y] = x;
        }
        else {
            parent[x] = y;
        }
    }
}

---

4. 결과 및 회고

다른 사람이 푼 코드와 비교함으로써 내 코드가 성능이 좋지 않다는 것을 깨달았던 것 같다.

그래서 개선한 과정도 의미 있었다. 코드 작성할 때 너무 직관적으로 생각하지 말도록 해야겠다. 뿌듯한 문제이당ㅎㅎ