백준 16234번 : 인구 이동 풀이(Java)

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

16234번: 인구 이동

Solution

1. 이 문제는 BFS + 시뮬레이션 문제이다. 국경선을 여는 것도, 인구를 이동시키는 것도 모두 BFS로 풀었다.

2. 먼저, main 역할을 하는 메서드에서는, 더 이상 열리는 국경선이 없을 때 까지 국경선 열기 -> 인구 이동하기 -> 국경선 열기 -> ... 를 반복해야 한다.

3. 그럼 결국 구현해야 할 것은

1. 국경선을 열기(즉, 가능한 국가들 끼리 서로 연결하는 것)
2. 인구 이동하기(연결된 국가들의 인구수를 합치고, 총 인구 수 / 국가 수 로 업데이트 해주기

이다.

 

4. 국경선을 여는 기능(그룹 기능)

먼저, 그룹을 나타내는 int[N][N] 배열을 만들어준다. 이름은 connected 로 했다. 또한 연합이 되는 국가가 하나도 없다면 main 메서드에서 반복문을 끝내기 위해서, atLeastOneOpened 라는 boolean 변수를 만들었다.  

• N*N 의 map을 돌면서, 아직 그룹에 포함되지 않은 나라라면, 그 나라부터 BFS 를 돌면서 "연합"을 만든다. 1번 연합, 2번 연합... 으로 이어질 것이다.
• 그럼 connected[r][c] 의 값이 0인 곳이, 연합에 포함되지 않은 나라이다. 그 곳부터 BFS 를 돌면 된다!
• BFS 를 돌면서 연합에 넣기 전에, 둘의 인구 수 차이가 L이상 R이하라면 연합에 넣어준다. 연합에 넣는다는 의미는, connected[nextR][nextC] 의 값을 connected[r][c] 의 값으로 바꿔주면 된다는 것이다. 이 때, atLeastOneOpened 를 true 로 만들어 줘서 반복문이 종료되지 않고 인구 이동이 일어나게 해준다.

5. 인구 이동 기능

connected 배열을 참고해서, 마찬가지로 N*N 배열을 돌며 연합인 국가들의 인구 수를 모두 합해준다. BFS가 끝난다면 해당 그룹의 모든 국가들의 인구수를 다 더해줬다는 의미이므로, 이제 map 의 인구 수를 갱신해줘야 한다.

이 때 주의할 점이 있다(시간 초과)

 

나는 값이 작길래 별 생각 없이, 각 나라가 해당 연합의 나라인지 나타내는 boolean 2차원 배열을 만들고 N*N 돌면서 연합일 경우 총 인구 수 / 국가 수 로 갱신해줬는데, 이렇게 하면 O(N^4) 의 시간 복잡도가 나오므로 80% 쯤에서 터졌었다. 그래서 생각한 방법은, BFS 를 돌면서 해당 연합인 경우 ArrayList 에 넣어서 기록을 해주고, BFS 가 끝날 때 ArrayList 를 돌면서 갱신해줬고 통과했다.

 

Source Code

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    private static BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));
    private static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    private static int N,L,R,RL;
    private static final int UP=0,RIGHT=2,DOWN=1,LEFT=3;
    private static int[][] map;
    private static int[][] connected;
    private static int[] dx = {-1,1,0,0};
    private static int[] dy = {0,0,1,-1};

    private static class Node {
        int r;
        int c;
        int group;

        public Node(int r, int c, int group) {
            this.r = r;
            this.c = c;
            this.group = group;
        }
    }

    public static void main(String[] args) throws IOException {
        input();
        solve();
        bufferedReader.close();
        bufferedWriter.close();
    }
    
    private static void input() throws IOException {
        StringTokenizer nlr = new StringTokenizer(bufferedReader.readLine());
        N = Integer.parseInt(nlr.nextToken());
        L = Integer.parseInt(nlr.nextToken());
        R = Integer.parseInt(nlr.nextToken());
        RL = R-L;
        map = new int[N][N];
        for(int i = 0 ; i < N; i++) {
            StringTokenizer line = new StringTokenizer(bufferedReader.readLine());
            for(int j = 0 ; j < N; j++) {
                map[i][j] = Integer.parseInt(line.nextToken());
            }
        }
    }

    private static boolean openLine() {
        connected = new int[N][N];
        int group = 1;
        boolean atLeastOneOpened = false;
        for(int r = 0; r < N; r++) {
            for(int c = 0; c < N; c++) {
                if(connected[r][c] != 0) continue; // 이미 연결된 애들은 넘어간다.
                Queue<Node> queue = new LinkedList<>();
                queue.add(new Node(r, c, group));
                connected[r][c] = group++;
                while (!queue.isEmpty()) {
                    Node before = queue.poll();
                    int sr = before.r;
                    int sc = before.c;
                    int sg = before.group;
                    for(int d = 0; d < 4; d++) {
                        int nr = sr + dx[d];
                        int nc = sc + dy[d];
                        if(nr < 0 || nc < 0 || nr >= N || nc >= N) continue;
                        if(connected[nr][nc] != 0) continue;
                        int next = map[nr][nc];
                        int howManyDiff = Math.abs(map[sr][sc] - next);
                        if(howManyDiff >= L && howManyDiff <= R) {
                            connected[nr][nc] = connected[sr][sc];
                            atLeastOneOpened = true;
                            queue.add(new Node(nr, nc, sg));
                        }
                    }
                }
            }
        }
        return atLeastOneOpened;
    }
    private static void checkLine() {
        for(int r = 0 ; r < N; r++) {
            for(int c = 0 ; c < N; c++) {
                System.out.print(connected[r][c] + " ");
            }
            System.out.println();
        }
        System.out.println("===========");
    }

    private static void printMap() {
        for(int r = 0 ; r < N; r++) {
            for(int c = 0 ; c < N; c++) {
                System.out.print(map[r][c] + " ");
            }
            System.out.println();
        }
        System.out.println("===========");
    }

    private static void move() {
        boolean[][] visited = new boolean[N][N];
        for(int r = 0 ; r < N; r++) {
            for(int c = 0 ; c < N; c++) {
                if(visited[r][c]) continue; // 이미 처리한 곳이라면 넘어가기
                ArrayList<Node> inGroup = new ArrayList<>(); // 해당 그룹에 있는 노드들을 담아두기
                int populationSum = map[r][c]; // 해당 그룹의 총 인구 수
                Queue<Node> queue = new LinkedList<>();
                queue.add(new Node(r, c, connected[r][c]));
                inGroup.add(new Node(r, c, connected[r][c]));
                while (!queue.isEmpty()) {
                    Node before = queue.poll();
                    int sr = before.r;
                    int sc = before.c;
                    visited[sr][sc] = true;
                    int sg = before.group;
                    for(int d = 0; d < 4; d++) {
                        int nr = sr + dx[d];
                        int nc = sc + dy[d];
                        if(nr < 0 || nc < 0 || nr >= N || nc >= N) continue;
                        if(visited[nr][nc]) continue;
                        if(connected[nr][nc] == sg) {
                            visited[nr][nc] = true;
                            populationSum += map[nr][nc];
                            queue.add(new Node(nr,nc,sg));
                            inGroup.add(new Node(nr, nc, sg));
                        }
                    }
                }
                for(Node x : inGroup) {
                    map[x.r][x.c] = populationSum / inGroup.size();
                }
            }
        }
    }

    private static void solve() {
        int count = 0;
        while (true) {
            if(!openLine()) {
                break;
            }
            //printMap();
            //checkLine();
            move();
            //printMap();
            count++;
        }
        System.out.println(count);
    }
}