[백준 / Java] 16234: 인구 이동 (BFS)

난이도: Gold 4

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

 

이 문제는 같은 영역끼리 묶어서 그 영역의 인구수의 평균만큼 이동을 시켜야 한다.

처음에는 영역 체크를 boolean 배열로 만들어서 조건에 해당하면 전부 true로 체크하여서 모두 같은 영역으로 처리하여 문제를 풀었는데, 그렇게 하면 안되고 영역 체크를 int 배열을 만들어서 국경선으로 구별하여 각각 다른 영역으로 처리해주어야 한다.

 

말로만 보면 이해가 안될 것이다. 그림을 보자.

 

 

초기 배열은 이렇다. 처음에는 국경선을 먼저 열어야 한다.

국경선을 여는 조건은 인접한 칸(상, 하, 좌, 우)과의 인구 차이가 10명 이상 50명 이하일 경우이다.

 

인접한 칸과의 인구 차이가  10명 이상 50명 이하일 경우, 국경선을 열었다.

굵은 선으로 둘러쌓여있는 칸은 모두 같은 영역이다.

조건에 해당하는 국경선을 모두 열었으니 이제 인구 이동을 시작해보자.

인구 이동은 같은 영역의 인구수의 평균만큼 이동해야 한다.

즉, 같은 영역의 배열 값을 모두 더해서 영역의 개수만큼 나누면 된다.

여기서는 (20 + 90 + 80 + 100 + 60 + 70 + 70 + 20 + 30 + 40 + 50 + 20 + 10) / 13 = 50 (소수점 버림) 만큼 이동하면 된다.

 

자꾸 같은 영역이라고 언급을 하는데, 여기서는 국경선이 뚫려있어서 같은 영역이 1개이지만, 이후에는 다른 영역으로 각각 쪼개질 수도 있기 때문에 같은 영역이라고 말을 하는 것이다.

이제 인구 이동을 시작해보자.

 

 

같은 영역은 모두 50만큼 인구 이동을 시켜주고, 국경선을 닫았다.

1일차 인구 이동이 끝난 것이다.

이제부터는 2일차이다. 날짜가 바뀌었으니 위 과정을 다시 반복해야 한다.

인접한 칸과의 인구 차이가 10명 이상 50명 이하일 경우, 2일차 인구 이동을 할 수 있다.

 

인접한 칸과의 인구 차이가  10명 이상 50명 이하일 경우, 국경선을 열었다.

굵은 선으로 둘러쌓여있는 칸은 모두 같은 영역이다.

 

그런데 아까와는 다르게 영역이 3개로 나뉘었다. 아까처럼 모두 같은 영역으로 처리해서 평균을 구하면 절대 안된다.

각각 다른 영역으로 취급하고, 각 영역의 평균만큼 영역 내에서만 인구 이동을 시켜주어야 한다.

그러므로 영역 체크 배열을 int로 만들어주어서 1번째 영역, 2번째 영역, 3번째 영역 등으로 나누어주어야 한다.

하지만 꼭 영역 배열의 값이 1, 2, 3처럼 순차적일 필요는 없다. 같은 영역끼리는 같은 숫자이기만 하면 된다. 

위와 같은 경우를 예를 들면,

 

1 2 2 0

1 2 0 0

0 0 8 0

0 8 8 8

 

영역 배열이 이런 식이어도 영역 구분은 확실하게 되기 때문에 상관 없다.

이제 인구 이동을 시켜야 한다. 인구 이동은 각 영역의 평균만큼 하면 된다고 했다.

 

빨간색 영역: (10 + 50) / 2 = 30

파란색 영역: (100 + 50 + 50) / 3 = 66 (소수점 버림)

초록색 영역: (50 + 50 + 100 + 50) / 4 = 62 (소수점 버림)

 

각 영역마다 인구 이동을 다르게 해주어야 한다.

이제 인구 이동을 시작해보자.

 

 

이렇게 각 영역마다 인구 이동을 다르게 해주었다.

인구 이동을 마친 후, 국경선을 닫자.

 

같은 영역끼리 인구 이동을 시켜주고, 국경선을 닫았다.

2일차 인구 이동이 끝난 것이다.

이제부터는 3일차이다. 날짜가 바뀌었으니 위 과정을 다시 반복해야 한다.

인접한 칸과의 인구 차이가 10명 이상 50명 이하일 경우, 3일차 인구 이동을 할 수 있다.

 

 

인접한 칸과의 인구 차이가  10명 이상 50명 이하일 경우, 국경선을 열었다.

굵은 선으로 둘러쌓여있는 칸은 모두 같은 영역이다. 이번에도 아까처럼 영역이 나뉘었다. 

 

빨간색 영역: (30 + 66) / 2 = 48 (소수점 버림)

파란색 영역: (66 + 50 + 30 + 66 + 50 + 50 + 50 + 62 + 50 + 50 + 62 + 62) / 12 = 54 (소수점 버림)

 

각 영역마다 평균을 구했다. 이제 인구 이동을 시작해보자.

 

 

이렇게 각 영역마다 인구 이동을 다르게 해주었다.

인구 이동을 마친 후, 국경선을 닫자.

 

 

같은 영역끼리 인구 이동을 시켜주고, 국경선을 닫았다.

3일차 인구 이동이 끝난 것이다.

이제부터는 4일차이다. 날짜가 바뀌었으니 위 과정을 다시 반복해야 한다.

인접한 칸과의 인구 차이가 10명 이상 50명 이하일 경우, 4일차 인구 이동을 할 수 있다.

 

그러나, 인구 차이가 10명 이상 50명 이하인 인접한 칸이 존재하지 않는다.

그렇다면 인구 이동은 3일로 끝이 나는 것이다.

 

좀더 확실하게 정리된 표를 보고 싶다면, 다음 링크를 참고하면 좋다. 필자는 이 글에서 많은 도움을 받았다.

https://www.acmicpc.net/board/view/114563

 

 

평균 값을 각 영역에 할당해주는 코드에 대해서 설명을 하기에는 너무 지저분하게 작성해서 생략하였다.

그래도 코드에 설명을 한 줄 한 줄 자세히 적어놓았다.

자, 그럼 이제 코드를 보자.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;
 
public class P16234_인구이동 {
    static int N;                        // 땅의 행, 열 개수
    static int L, R;                    // L명 이상, R명 이하
    static int[] dx = {-1, 0, 1, 0};    // 상, 하 이동
    static int[] dy = {0, -1, 0, 1};    // 좌, 우 이동
    static int[][] A;                    // 2차원 땅 배열
    static boolean[][] visited;            // 2차원 방문 여부 배열
    static int[][] unionNumber;            // 2차원 연합국 번호 배열
    static int number;                    // 연합국 구분 변수 (같은 영역은 같은 number)
    static Queue<int[]> queue = new LinkedList<>();    // bfs 사용을 위한 큐
    
    static class Union {
        int people;        // 연합의 인구 수
        int space;        // 연합을 이루고 있는 칸의 개수
        
        Union(int people, int space) {
            this.people = people;
            this.space = space;
        }
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());    
        L = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());    
        A = new int[N][N];
        int days = 0;        // 인구 이동 발생 일 수
        
        // 2차원 땅 배열 초기화 (각 나라의 인구 수 초기화)
        for (int r = 0; r < N; r++) {
            st = new StringTokenizer(br.readLine());
            for (int c = 0; c < N; c++) {
                A[r][c] = Integer.parseInt(st.nextToken());    // 각 나라의 인구 수 할당
            }
        }
        
        // n일차 인구 이동 (while문 한 번 수행 = 하루 인구 이동)
        while (true) {
            // 인구 이동이 시작하는 날에는 모든 정보가 초기화되어야 함
            
            // 연합국의 정보를 저장하는 맵
            // 키: 각 연합의 번호(unionNumber의 배열 값), 값: 각 연합의 인구 수와 칸의 개수가 담겨있는 객체
            HashMap<Integer, Union> union = new HashMap<>();
            visited = new boolean[N][N];    // 2차원 방문 배열 초기화
            unionNumber = new int[N][N];    // 2차원 연합국 번호 배열 초기화
            number = 0;                        // 연합국 구분 변수(같은 영역은 같은 number)
            
            // 모든 칸을 BFS로 탐색하여 국경선을 열어줌
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (!visited[i][j]) {        // 해당 칸을 방문하지 않았다면
                        number++;                // 연합국 구분 변수 1 증가
                        openBorderBfs(i, j);    // 해당 칸부터 국경선을 여는 bfs 수행
                    }
                }
            }
            
            boolean existed = existOpenedBorder();    // 국경선이 열린 곳이 존재하는지 확인하기
            
            if (!existed) {        // 국경선이 열린 곳이 존재하지 않는다면
                System.out.println(days);    // 현재 인구 이동 발생 일 수 출력
                return;                        // 인구 이동 종료
            }
            
            // 모든 칸을 탐색
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    // 해당 연합국 번호 배열 값이 0이 아니라면 연합국인 영역
                    if (unionNumber[i][j] != 0) {    
                        // 연합국의 정보를 저장하는 맵에 연합국 번호 배열 값인 키가 있다면
                        if (union.containsKey(unionNumber[i][j])) {
                            // 연합의 인구 수와 칸의 개수가 담겨있는 객체를 
                            // 맵에서 연합국 번호 배열 값인 키로 얻어오기
                            Union temp = union.get(unionNumber[i][j]);
                            temp.people += A[i][j];    // 해당 연합의 인구 수 증가
                            temp.space++;            // 해당 연합의 칸 수 증가
                            union.put(unionNumber[i][j], temp);    // 맵에 갱신한 정보 저장
                        } else {    // 연합국의 정보를 저장하는 맵에 연합국 번호 배열 값인 키가 없다면
                            // 맵에서 연합국 번호 배열값을 키로 갖는 객체 새로 생성
                            // 초기에는 값인 연합 객체에 A[i][j]명과 1칸을 저장
                            union.put(unionNumber[i][j], new Union(A[i][j], 1));
                        }
                    }
                }
            }
            
            // 연합국의 키를 목록으로 갖는 Set 객체 리턴
            Set<Integer> keySet = union.keySet();
            
            // 맵의 키(연합국 번호)로 탐색
            for (int unionNum : keySet) {
                // 연합의 객체를 맵에서 연합국 번호인 키로 얻어오기
                Union uni = union.get(unionNum);
                // 연합국들에게 이동시킬 인구 수 구하기 => 연합의 평균 구하기
                int spacePeopleNumber = uni.people / uni.space;
                
                // 모든 칸을 탐색
                for (int i = 0; i < N; i++) {
                    for (int j = 0; j < N; j++) {
                        // 맵의 키(연합국 번호)가 해당 연합국 번호 배열값과 같다면
                        if (unionNumber[i][j] == unionNum) {
                            // 해당 영역에 연합의 평균을 대입 (연합국에 인구 이동)
                            A[i][j] = spacePeopleNumber;    
                        }
                    }
                }
            }
            
            days++;        // 인구 이동이 끝났으므로 1일차 종료
        }
    }
    
    // 국경선을 여는 메소드
    public static void openBorderBfs(int a, int b) {
        queue.add(new int[] {a, b});    // 현재 칸을 큐에 삽입
        visited[a][b] = true;            // 현재 칸을 방문 체크
        
        // 큐가 빌 때까지 반복
        while (!queue.isEmpty()) {
            int[] now = queue.poll();    // 현재 칸
            
            for (int i = 0; i < 4; i++) {
                int x = now[0] + dx[i];    // 인접한 칸으로 x좌표 이동
                int y = now[1] + dy[i];    // 인접한 칸으로 y좌표 이동
                
                // 인덱스가 유효 범위에서 벗어난다면 건너뛰기
                if (x < 0 || y < 0 || x >= N || y >= N) {
                    continue;
                }
                
                if (visited[x][y]) {    // 인접 칸을 이미 방문했다면 건너뛰기
                    continue;
                }
                
                // 현재 칸과 인접 칸의 인구 차이 구하기
                int diff = Math.abs(A[now[0]][now[1]] - A[x][y]);
                
                // 인접한 칸과의 인구 차이가 L명 이상 R명 이하라면
                if (diff >= L && diff <= R) {
                    queue.add(new int[] {x, y});    // 인접 칸을 큐에 삽입
                    visited[x][y] = true;            // 인접 칸을 방문 체크
                    // 연합국 구분 변수를 현재 칸의 연합국 번호 배열 값에 넣기
                    unionNumber[now[0]][now[1]] = number;    
                    // 연합국 구분 변수를 인접 칸의 연합국 번호 배열 값에 넣기
                    unionNumber[x][y] = number;
                }
            }
        }
    }
    
    // 국경선이 열린 곳이 존재하는지 확인하는 메소드
    public static boolean existOpenedBorder() {
        boolean existed = false;    // 국경선 열린 곳 존재 여부 변수
        
        // 모든 칸을 탐색
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (unionNumber[i][j] != 0) {    // 해당 연합국 번호 배열 값이 0이 아니라면 연합국인 영역 
                    existed = true;                // 국경선 열린 곳 존재 여부 변수를 true로 변경
                    return existed;                // 국경선 열린 곳 존재 여부 변수(true)를 바로 리턴
                }
            }
        }
        
        // 위의 칸을 모두 탐색했는데도 해당 문장을 만났으면 무조건 false값임
        // 국경선 열린 곳 존재 여부 변수(false)를 리턴
        return existed;        
    }
}