백준 문제 16234 - 인구 이동.

인구 이동을 1회한다고 함은,

map을 2중포문 돌면서 각 국가에 대해 연합을 맺을 수 있는 영역을 체크하여 인구 수를 조정하는 것입니다. 

   

만약 이렇게 3개의 연합으로 나뉜다고 가정했을 때, 각 연합에 포함된 국가의 인구수는 [하나의 연합내 모든 인구수/하나의 연합내 국가수] 으로 변경해주어야 합니다. 

 

이를 위해 필자는

1.각 국가에 대해 연합을 맺을 수 있는 영역을 찾기 위해 BFS로 탐색했습니다.

연합마다 분류하기 위해 openNation[][]에 areaNumber를 저장했습니다. 

동일한 areaNumber를 가진 국가들은 연합되어 있음을 의미합니다.  

<-openNation[][]

2.하나의 연합이 완성되면 그 즉시 map의 데이터를 변경했습니다. 

즉 특정 국가를 시작점으로 BFS 탐색이 종료되면, 원본 입력데이터 map의 데이터를 그 연합의 평균 인구수로 조정해줍니다.

 

 

위와 같은 과정을 인구이동을 하지 못할때까지 반복합니다. 

 

코드는 다음과 같습니다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    int[][] directions = { { 0, 1 }, { -1, 0 }, { 0, -1 }, { 1, 0 } };
    int l;
    int r;
 
    public static void main(String[] args) throws IOException {
        Main main = new Main();
        main.move();
    }
 
    public void move() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
        int mapSize = Integer.parseInt(st.nextToken());
        l = Integer.parseInt(st.nextToken());
        r = Integer.parseInt(st.nextToken());
 
        int[][] map = new int[mapSize][mapSize];
        int peopleMoveCnt = 0;
        int areaNumber = 0;
 
        for (int i = 0; i < mapSize; i++) {
            StringTokenizer row = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < mapSize; j++) {
                map[i][j] = Integer.parseInt(row.nextToken());
            }
        }
 
        while (true) { //인구 이동을 할 수 없을때까지 반복.
            boolean move = false; //인구 이동 여부.
            int[][] openNations = new int[mapSize][mapSize];
            
            for (int i = 0; i < mapSize; i++) {
                for (int j = 0; j < mapSize; j++) {
                    if (openNations[i][j] != 0) { //이미 연합을 맺은 국가이면, BFS탐색을 했었다는 의미이므로 skip
                        continue;
                    }
 
                    areaNumber++;
                    int nationPeopleSum = 0;
                    int nationCnt = 0;
 
                    Queue<Point> queue = new LinkedList<>();
                    queue.add(new Point(i, j));
                    openNations[i][j] = areaNumber;
                    
                    //BFS탐색 시작
                    while (!queue.isEmpty()) {
                        Point curPoint = queue.poll();
                        nationPeopleSum += map[curPoint.x][curPoint.y];
                        nationCnt++;
                        
                        for (int[] direction : directions) {
 
                            int newI = curPoint.x + direction[0];
                            int newJ = curPoint.y + direction[1];
 
                            if (newI >= 0 && newJ >= 0 && newI < mapSize && newJ < mapSize
                                    && Math.abs(map[curPoint.x][curPoint.y] - map[newI][newJ]) >= l
                                    && Math.abs(map[curPoint.x][curPoint.y] - map[newI][newJ]) <= r
                                    && openNations[newI][newJ] == 0) {
                                queue.add(new Point(newI, newJ));
                                openNations[newI][newJ] = areaNumber;
                            }
 
                        }
 
                    }
                    //BFS탐색 종료
 
                    //하나의 BFS탐색에서 연합국이 없으면 다음 칸의 BFS탐색을 하도록 skip
                    if(nationCnt ==1) {
                        continue;
                    }
                    
                    //하나의 BFS탐색에서 연합국이 있으면, 
                    //1. 인구 이동이 가능하므로 move = true;
                    move = true;
                    //2. 원본 입력값 map의 인구수 조정.
                    for (int k = 0; k < mapSize; k++) {
                        for (int r = 0; r < mapSize; r++) {
                            if (openNations[k][r] == areaNumber) {
                                map[k][r] = nationPeopleSum / nationCnt;
                            }
                        }
                    }
 
                }
            }
 
            //map을 전체 탐색하고나서 인구 이동이 없었으면, while문 종료.
            if (!move) {
                System.out.println(peopleMoveCnt);
                break;
            }
            //map을 전체 탐색하고나서 인구 이동이 있으면, 인구 이동 수 증가시키고 다시 map 전체를 탐색. 
            peopleMoveCnt++;
            
 
        }
 
    }
 
    public class Point {
        int x;
        int y;
 
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}