백준 16234번 인구 이동 :: 마이구미

이 글은 백준 알고리즘 문제 16234번 "인구 이동" 을 풀이한다.

문제는 BFS 를 통해 풀이한다.

삼성 SW 역량 테스트에서 출제된 문제이다.

문제 링크 - https://www.acmicpc.net/problem/16234

BFS - http://mygumi.tistory.com/102

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

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

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

• 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루동안 연다.
• 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.
• 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.
• 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.
• 연합을 해체하고, 모든 국경선을 닫는다.

각 나라의 인구수가 주어졌을 때, 인구 이동이 몇 번 발생하는지 구하는 프로그램을 작성하시오.

문제는 "인접한 칸", "이동" 등으로 파악할 수 있는 전형적인 탐색을 요구하는 문제가 된다.

DFS, BFS 어느 것으로 접근하더라도 크게 상관없다.

본인은 BFS 를 사용한 풀이를 다룬다.

문제는 단순히 서로 연결되어있는 나라를 탐색하여, 연결된 나라는 (연합의 인구수) / (연합 개수) 로 인구 수를 업데이트 해주면 된다.

1. 연합 국가 탐색.
2. 탐색된 연합 국가들의 인구수 업데이트.

위 2가지 과정을 반복해주면 된다.

주의할 점은 "추적", "방문 여부", "인구 이동 발생의 기준" 이다.

추적은 연합된 나라들의 인구수 업데이트를 위해서는 탐색을 하면서 연결되어있는 나라의 위치를 추적해줘야한다.

그래야 추적된 결과를 통해 인구 수를 업데이트 해줄 수 있다.

방문 여부는 인구 이동 발생의 기준과 밀접하다.

방문 여부를 언제 초기화해야 할지는 인구 이동 발생의 횟수 증가에 달렸기 때문이다.

이 내용들은 그림을 통해 이해하면 쉽게 받아들일 수 있다.

입력값은 문제에서 제시하고 있는 마지막 입력을 기준으로 한다.

인구 이동이 2번 이상 발생하는 예를 이해해야만 문제를 해결할 수 있다.

4 10 50
10 100 20 90
80 100 60 70
70 20 30 40
50 20 100 10

나라를 순서대로 탐색하는 과정에서, "10", "100" 은 인접한 나라 중 연합 조건이 성립되지 않은 상황이다.

그리고 "20" 을 기준으로 연합 국가를 만든 그림이다.

(연합을 이루는 것이 중점이기 때문에, 문제에서 관계를 표현하는 점선은 사실상 신경쓰지 않아도 된다.)

20 을 기준으로 연합 국가를 만들고 인구 수를 업데이트 해준 후, 계속해서 순서대로 탐색한다.

하지만 이미 방문 했거나, 더이상 연합 성립에 만족하는 경우는 존재하지 않는다.

이렇게 첫번째 인구 이동이 끝이 난다.

그리고 다음 인구 이동을 진행한다.

이것이 인구 이동의 발생 기준이다.

본인은 이것 때문에 혼란 및 시간을 썼다.

2번째 인구 이동을 시작한다.

이때 이전 과정은 인구 수를 제외한 모두 초기화 된다.

2번째 인구 이동 탐색 중 연합 국가를 성립하는 경우를 찾은 후, 연합국에 대한 인구수를 업데이트 했다.

그리고 다른 연합국 존재를 위해 계속 진행한다.

이렇게 2번째 인구 이동 탐색이 끝난다.

다시 3번째 인구 이동 탐색을 위해 진행한다.

이런 식으로 진행되는 모습을 볼 수 있다.

인구 이동 탐색을 진행하면서, 그 과정 중 연합국이 한번도 없었다면, 더이상 진행할 필요가 없다.

그러므로, 모든 과정을 멈추고, 결과를 출력하면 된다.

Github - https://github.com/hotehrud/acmicpc/blob/master/SAMSUMG/16234.java

static boolean[] visited = new boolean[10001];
static int[][] map = new int[51][51];
static ArrayList<Integer> track = new ArrayList<Integer>();
static int[] dx = { -1, 0, 1, 0 };
static int[] dy = { 0, -1, 0, 1 };
static int N, L, R, ans;
 
private void solve() {
    N = sc.nextInt();
    L = sc.nextInt();
    R = sc.nextInt();
 
    for (int i = 0; i < N; i++) {
        String[] c = sc.readLine().split(" ");
        int size = c.length;
 
        for (int j = 0; j < size; j++) {
            map[i][j] = Integer.parseInt(c[j]);
        }
    }
 
    boolean flag = true;
    while (flag) {
        Queue<Integer> q = new LinkedList<Integer>();
        visited = new boolean[10001];
        flag = false;
        ans++;
        // ?번째 인구 이동 탐색
        for (int i = 0; i < N * N; i++) {
            if (visited[i]) {
                continue;
            }
            track = new ArrayList<Integer>();
 
            int r = i / N;
            int c = i % N;
            q.add(i);
            visited[i] = true;
            track.add(i);
            int total = map[r][c];
            int n = 1;
 
            while (!q.isEmpty()) {
                int v = q.poll();
                r = v / N;
                c = v % N;
 
                for (int k = 0; k < 4; k++) {
                    int nx = c + dx[k];
                    int ny = r + dy[k];
 
                    if (0 <= nx && nx < N && 0 <= ny && ny < N) {
                        int next = ny * N + nx;
 
                        if (visited[next]) {
                            continue;
                        }
 
                        int count = map[ny][nx];
                        int pivot = map[r][c];
                        if (L <= Math.abs(count - pivot) && Math.abs(count - pivot) <= R) {
                            // 연합국 조건 성립
                            flag = true;
                            q.add(next);
                            visited[next] = true;
                            track.add(next);
                            total += map[ny][nx];
                            n++;
                        }
                    }
 
                }
            }
            // 연합국 인구 수 업데이트
            int updateN = total / n;
            if (track.size() > 1) {
                for (int v : track) {
                    r = v / N;
                    c = v % N;
                    map[r][c] = updateN;
                }
            }
 
        }
    }
    System.out.println(ans - 1);
}