백준 16234번 : 인구 이동 자바

 

🧫 문제 분석

 

✔️ 출처

인구 이동 골드4

 

📖 문제

 

랜덤 문제를 돌리다가 나왔다. 그래프 탐색 냄새가 솔솔 난다. BFS를 사용하면 될것 같다. 

 

1. 한 나라의 좌우 상하로 인접한 다른 나라와의 인구차를 M명이라 했을 때 L <= M <= R 을 만족해야한다.

2. 조건을 만족한 나라들과는 연합을 하여 국경선을 하루 연다. 

3. 인구가 이동하며 각 나라의 인구수는 (연합 인구수 / 연합한 나라 개수) 가 되며 소수점은 버린다. 

4. 이동후 연합 해지 및 모든 국경선을 닫는다.

5. 인구 이동이 없을때까지 반복한다.

6. 인구 이동이 며칠동안 발생했는지가 문제이다.

 

 

내가 생각한 방법

1. 우선 연합가능한 나라들을 찾고, 그 나라에 연합 번호를 매기며 각 인구수를 더해놓는다. 

2. 연합은 1개 이상 생길 수 있다. 

3. 만약 1번 연합이면 1번 연합 나라들의 수를 저장했다가 map에 인구 이동이 된 나라들의 수를 {연합번호 : 인구수 }로 저장한다.

4. 인구 이동을 한 날을 하루 추가하고, 인구 이동이 없을때까지 반복한다.

 

예제 4번을 예시로 들면 

예제 출력은 2이다.

첫 번째 연합, 연합 번호를 매긴 상태이다.

이때 인구 이동 후 1번 연합나라들의 인구수는 142 / 7 = 20명 이다. 

두 번째 연합

인구 이동 후 연합 가능한 나라들을 살펴보니 또 있는 것을 알 수 있다.

또 한번 연합 번호를 매기고 인구 이동을 한다.

50 / 3 = 16이 되므로 1 연합의 3나라들은 16명이 된다. 

이 후는 더이상 인구 이동이 불가능하므로 총 2일동안 인구 이동이 발생했다.

 

---

🔅 문제 풀이

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


public class Main {

    static int[] dxarr = {0,0,1,-1};
    static int[] dyarr = {1,-1,0,0};
    static int[][] union; // 연합 그룹 번호도 마킹
    static HashMap<Integer, Integer> map = new HashMap<>();
    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());

        int n = Integer.parseInt(st.nextToken());
        int L = Integer.parseInt(st.nextToken());
        int R = Integer.parseInt(st.nextToken());
        int[][] lands = new int[n][n];
        union = new int[n][n];
        int answer = 0;

        // 땅 배열 값 초기화
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < n; j++) {
                lands[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        int maxUnionNum = bfs(lands, L, R);

        while(maxUnionNum > 0) {

            for (int i = 0; i < lands.length; i++)  {
                for (int j = 0; j < lands[0].length; j++) {

                    if (union[i][j] > 0) {
                        int tmp = map.getOrDefault(union[i][j], 0);
                        if (tmp > 0)  lands[i][j] = tmp;
                    }
                }
            }
            
            answer++;
            union = new int[n][n]; // 인구 이동이 된 후 다시 연합 가능한 나라 조사를 위해 방문기록 초기화
            maxUnionNum = bfs(lands, L, R);
        }
        
        bw.write(answer + "\n");
        bw.flush();
        bw.close();
    }

    public static int bfs(int[][] land, int L, int R) {
        Queue<int[]> q = new LinkedList<>();
        int unionNum = 1;

        for (int i = 0; i < land.length; i++) {
            for (int j = 0; j < land[0].length; j++) {
                if (union[i][j] == 0) {
                    q.add(new int[] {i,j});
                    union[i][j] = unionNum++;
                    int count = 0; // 연합이 없는 땅 체크
                    int popular = 0;

                    // 연합 땅 번호 새기기
                    while(!q.isEmpty()) {
                        int[] landPoint = q.poll();
                        popular += land[landPoint[0]][landPoint[1]];

                        for (int k = 0; k < 4; k++) {
                            int dy = landPoint[0] + dyarr[k]; // 행
                            int dx = landPoint[1] + dxarr[k]; // 열

                            if (dx >= 0 && dx < land[0].length && dy >= 0 && dy < land.length) {
                                if (union[dy][dx] == 0) {
                                    int gap = land[landPoint[0]][landPoint[1]] - land[dy][dx];
                                    if (gap < 0) gap *= -1;

                                    if (gap < L || gap > R) continue; // 인구수 차가 L ~ R이 아니면 다음땅으로
                                    union[dy][dx] = union[i][j];
                                    q.add(new int[] {dy, dx});

                                    count++;
                                }
                            }
                        }
                    }

                    if (count == 0){
                        unionNum--; // 연합이 없다면 연합번호 - 1
                        union[i][j] = 0; // 연합이 없기에 연합 번호를 없앤다.
                    }else {
                        map.put(union[i][j], (popular / (count + 1))); // 연합 번호와 이동 후 인구수를 map에 저장
                    }
                }
            }
        }

        return unionNum - 1;
    }

}

---

 

ps. 사실 많은 시행착오를 겪었다. 연합 체크를 앞에서 해버려서 무한 루프에 빠지고.. , 연합이 없으면 연합번호를 제거해야하는데 제거하지 않아서 방문했던 모든 나라들에게 연합번호가 부여되서 인구수가 증가해버리는 사태까지 일어났다. 이번에 한 번 풀었으니 경험이 되었을 것이다ㅎㅎ

 

❗ 오답노트 / 필요한 지식

1. 정말정말 많은 시간을 썼다. 
2. 그래프 탐색 문제에서는 항상 visited를 생각해야한다. 방문한 곳은 더이상 방문하지 않게 한다던가, 아무튼 while(!p.isEmpty)에서 무한루프에 빠지지않게 잘 생각해서 짜자.
3. 부족한 그래프 탐색이니 많이 풀어보자.