BOJ 16234 - 인구 이동(Java)

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

16234번: 인구 이동

 

풀이

인구이동이 더 이상 불가능 할때 까지 계속해서 이동 반복

이동되는 구역을 visit[][]로 확인, 다시 탐색하지 않도록 예외 처리

 

- 인구 이동이 가능한지 확인

    - 인구 이동이 가능하다면 해당 구역 전체 인구 이동

    - bfs를 이용하여 인근 구역 탐색 -> L < abs( map[y][x]-map[ny][nx] ) < R이라면 이동 가능

    - 인구이동 구역 설정까지 bfs 탐색 반복

- 인구 이동이 가능하다면 날짜수 +1 

- 인구 이동이 불가능하다면 탐색 종료 및 날짜 출력

 

 

 

 

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

public class Main {
    static int N, L, R;
    static int[][] area;
    static boolean[][] visit;
    static int[] dy = {0, 1, 0, -1};
    static int[] dx = {1, 0, -1, 0};

    static class Pair {
        public int y;
        public int x;

        Pair(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));        

        area = new int[51][51];

        StringTokenizer st;
        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++) {
                area[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int date = 0;
        while (true) {
            visit = new boolean[51][51];
            // 모든 요소 탐색 후 이동 가능한 곳이 없다면 break
            if (!move())
                break;
            date++;
        }
        System.out.println(date);

    }
    // 인구이동이 있는지를 Return
    private static boolean move() {
        boolean flag = false;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (visit[i][j]) continue;
                // 탐문하지 않은 요소의 경우 bfs로 주변 요소로 이동가능한지 확인
                // 이동가능한 요소가 있을 경우 flag를 true로 갱신
                if (bfs(i, j)&&!flag)
                    flag = true;
            }
        }
        return flag;
    }

    private static boolean bfs(int i, int j) {
        visit[i][j] = true;
        int sum=area[i][j];
        LinkedList<Pair> q = new LinkedList<>();
        List<Pair> list = new ArrayList<>();
        list.add(new Pair(i, j));
        q.add(new Pair(i, j));

        int y, x, ny, nx;
        while (!q.isEmpty()) {
            Pair now= q.poll();
            y=now.y;
            x=now.x;

            for (int d = 0; d < 4; d++) {
                ny = y + dy[d];
                nx = x + dx[d];
                if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
                if(visit[ny][nx])continue;
                if((Math.abs(area[ny][nx]- area[y][x])>=L) && (Math.abs(area[ny][nx]- area[y][x])<=R)){
                    visit[ny][nx]=true;
                    q.add(new Pair(ny,nx));
                    list.add(new Pair(ny,nx));
                    sum+=area[ny][nx];
                }
            }
        }
        // 주변에 이동 가능한 요소가 없을 시 false return
        if(list.size()==1)
            return false;
        // 이동 가능한 요소가 있다면 각 요소의 값을 (인구 합/요소의 수)로 갱신, return true
        else{
            int size= list.size();
            for(int idx=0;idx<list.size();idx++){
                area[list.get(idx).y][list.get(idx).x]=sum/size;
            }
            return true;
        }
    }
}