[백준] 16234번 : 인구 이동

16234번: 인구 이동

[BFS]

나는 보통 visit를 boolean으로 하여 true/false로 구분하지만, 이런 영역을 나눠야 하는 문제에서는 int visit[][]로 하는 편이 좋다. 점(i, j)에서 인접한 점과의 차(a)가 l <= a <= r인 곳을 Queue에 넣으며 동시에 같은 영역이라고 생각한다. 큐에 넣으면서 반드시 동일 영역의 인구 수를 sum에 더해주고, 동일 영역의 개수가 몇 개인지도 계속 체크해주어야 한다.

 

Queue가 비었으면 동일한 영역 모든 곳의 값을 sum / cnt로 변경한다.

 

각 루프에서 초기화와 visit에 주의하자.

# Code </>

public class Main {

    static class Point{
        int y, x;
        public Point(int yy, int xx){
            y = yy; x = xx;
        }
    }
    static int[][] map = new int[50][50], visit;
    static int[] Y = {-1, 1, 0, 0}, X = {0, 0, -1, 1};
    static int n, l, r, cnt = 0, sum = 0, area = 0;

    static boolean isUnion(int y, int x){
        boolean flag = false;

        for(int a=0; a<4; a++){
            int ny = y+Y[a];
            int nx = x+X[a];

            if(ny < 0 || nx < 0 || ny >= n || nx >= n || visit[ny][nx] != 0) continue;

            if(Math.abs(map[y][x] - map[ny][nx]) >= l && Math.abs(map[y][x] - map[ny][nx]) <= r) {
                flag = true;
                break;
            }
        }
        return flag;
    }

    static boolean BFS(){
        boolean open = false;
        Queue<Point> Q = new LinkedList<>();

        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++) {
                cnt = 1;
                sum = map[i][j];

                if (visit[i][j] == 0 && isUnion(i, j)) {
                    open = true;
                    area++;
                    visit[i][j] = area;
                    Q.add(new Point(i, j));

                    while (!Q.isEmpty()) {
                        Point p = Q.poll();
                        int y = p.y;
                        int x = p.x;

                        for (int a = 0; a < 4; a++) {
                            int ny = y + Y[a];
                            int nx = x + X[a];

                            if (ny < 0 || nx < 0 || ny >= n || nx >= n || visit[ny][nx] != 0) continue;

                            if (Math.abs(map[y][x] - map[ny][nx]) >= l && Math.abs(map[y][x] - map[ny][nx]) <= r) {
                                cnt++;
                                sum += map[ny][nx];
                                visit[ny][nx] = area;
                                Q.add(new Point(ny, nx));
                            }
                        }
                    }
                    for (int a = 0; a < n; a++)
                        for (int b = 0; b < n; b++)
                            if (visit[a][b] == area)
                                map[a][b] = sum / cnt;
                }
            }

        return open;
    }

    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());

        for(int i=0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<n; j++)
                map[i][j] = Integer.parseInt(st.nextToken());
        }

        int time = 0;
        while(true){
            area = 0;
            visit = new int[50][50];
            if(!BFS()) break;
            time++;
        }

        System.out.println(time);
    }
}