[백준] 16234번 인구 이동

생각

Github - https://github.com/hellojdh/Code/blob/master/src/baekjoon/q10000/Q16234.java

각 나라의 인구가 적혀있는 2차 배열이 주어진다.
한 나라가 인접 나라와의 차이가 L이상 R이하일 경우 국경을 개방하고 인구이동이 시작된다.
인구의 이동은 국경을 개방한 나라들을 연합으로 취급하여 연합의 총 인구수/나라 수 로
진행된다. 인구 이동이 몇 번 발생하는지 출력하여라.

처음 생각

BFS 탐색을 통해 한 나라로 시작해서 국경을 개방할 수 있는 나라일 경우 같은 연합으로 번호를 지정해주면서 진행을 하였다. 방문 표시로 연합 번호를 사용해서 연합 번호가 부여되어 있을시에는 탐색에서 건너뛰게 구현하였다.

▶ 한 번의 BFS 탐색이 끝나면 다시 모든 배열을 탐색하면서 해당 연합 번호를 가지고 있는 나라들은 새로운 인구수를 적용시켜 주었다.

▶ 연합의 숫자와 총 인구수는 BFS 탐색을 하면서 늘려주었다.

다음 생각

연합이 안 만들어 질때까지 진행을 해야하기 때문에 while(true)를 이용해서 계속 탐색을 진행하도록 하였고, 연합이 모든 배열을 탐색해을 때 연합이 안 만들어진다면 break 문을 통해 반복문을 종료시켜 주었다.

다다음 생각

연합 번호를 가지고 방문 배열로 사용해 줬기 때문에 한 번의 BFS 탐색을 전부 돌면 다시 방문 배열을 0으로 초기화 해주어 다음 탐색에서도 사용할 수 있도록 해주었다.

방안

1) 같은 방식의 BFS 탐색을 여러번 진행할 수 있나를 묻고자한 문제같다.

2) 같은 연합 인구나누기를 전부 살펴보지 않고 BFS 탐색시 List에 넣어둔 후, 그 List에 담긴 영역들만 인구 나누기를 진행해 준다면 속도가 크게 빨라진다.

package baekjoon.q10000;
 
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class Q16234 {
    static int n,l,r;
    static int[][] arr;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        l = sc.nextInt(); // L명 이상
        r = sc.nextInt(); // R명 이하
        // 두 나라 인구 차이가 L명 이상 R명 이하면 국경선이 열린다.
        // 연합을 이루는 각 칸의 인구수는 
        // 연합 인구수 / 연합 이루는 칸의 개수 가된다.
        arr = new int[n][n];
        visited = new int[n][n];
        for(int i=0;i<n;i++) {
            for(int j=0;j<n;j++)
                arr[i][j] = sc.nextInt();
        }
        
        int result = 0;
        // 인구 이동이 안일어 날 때 까지
        while(true) {
            boolean check = false; // 인구 이동이 일어났나 확인하는 변수
            teamN = 0;
            for(int i=0;i<n;i++) {
                for(int j=0;j<n;j++) {
                    // 다른 연합이 아닐 경우만 체크
                    if(visited[i][j]==0) {
                        // 인구 이동이 일어났으면 true
                        if(solve(i,j)) check = true;
                    }
                }
            }
            if(check) result++; // 인구 이동이 일어났으면 +1
            else break; // 인구 이동이 일어나지 않았으면 종료
            
            // 다 살펴 봤으면 방문(연합 번호)초기화
            for(int i=0;i<n;i++) {
                for(int j=0;j<n;j++)
                    visited[i][j] = 0;
            }
        }
        System.out.println(result);
    }
    
    static int teamN;
    static int[][] visited;
    static int[][] dir = {{1,0},{0,1},{-1,0},{0,-1}};
    private static boolean solve(int x,int y) {
        Queue<Pair> queue = new LinkedList<>();
        teamN++; // 각각의 연합에 번호를 부여하기 위해서
        queue.add(new Pair(x, y));
        visited[x][y] = teamN;
        int tHuman = arr[x][y];
        int tCnt = 1;
        while(!queue.isEmpty()) {
            Pair t = queue.poll();
            
            for(int i=0;i<4;i++) {
                int tx = t.x+dir[i][0];
                int ty = t.y+dir[i][1];
                if(tx<0 || ty<0 || tx>=n || ty>=n) continue;
                // 방문 체크 & 연합 구별
                if(visited[tx][ty]!=0) continue;
                // 두 나라의 차이가 범위안이라면
                if(check(arr[t.x][t.y], arr[tx][ty])) {
                    visited[tx][ty] = teamN;
                    tCnt++; // 연합 수 세기
                    tHuman+=arr[tx][ty]; // 인구 수 더하기
                    queue.add(new Pair(tx, ty));
                }
            }
        }
        
        // 같은 연합 인구 나누기
        for(int i=0;i<n;i++) {
            for(int j=0;j<n;j++) {
                if(visited[i][j]==teamN) {
                    arr[i][j] = tHuman/tCnt;
                }
            }
        }
        // tCnt가 1보다 크다는 것은 인구이동이 일어 났다는 것이다.
        if(tCnt>1) return true;
        else return false;
    }
    
    // 국경 체크
    private static boolean check(int n1,int n2) {
        int t = Math.abs(n1-n2);
        // 두 나라의 차이가 l명이상 r명 이하라면
        if(t>=l&&t<=r) return true;
        else return false;
    }
    
    static class Pair{
        int x,y;
        Pair(int x,int y){
            this.x = x;
            this.y = y;
        }
    }
}