[백준] 16234번 : 인구 이동

문제

www.acmicpc.net/problem/16234

16234번: 인구 이동

문제해결방법

BFS를 돌면서 인구 이동이 발생하는지 확인하고, 만약 발생한다면 인구 이동을 시켜준다.

위 과정을 더 이상 인구 이동이 발생하지 않을 때까지 반복해준다.

코드

package baekjoon;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
 
public class Main16234_인구이동 {
 
    public static int N, min, max;
    public static boolean[][] v;
    public static int[][] map;
    public static int[][] dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    
    public static boolean bfs(int i, int j, boolean check) {
        boolean m = false;
        List<int[]> list = new ArrayList<>();
        int index = 0;
        list.add(new int[] {i, j});
        v[i][j] = check;
        int count = 1;
        int sum = map[i][j];
        while(index!=list.size()) {
            int[] cur = list.get(index++);
            for(int d=0; d<dir.length; d++) {
                int x = cur[0] + dir[d][0];
                int y = cur[1] + dir[d][1];
                if(x>=0 && x<N && y>=0 && y<N && v[x][y]!=check) {
                    int diff = Math.abs(map[x][y] - map[cur[0]][cur[1]]);
                    if(diff>=min && diff<=max) {
                        v[x][y] = check;
                        count++;
                        sum += map[x][y];
                        list.add(new int[] {x, y});
                    }
                }
            }
        }
        for(int s=0; s<list.size(); s++) {
            int[] cur = list.get(s);
            map[cur[0]][cur[1]] = sum/count;
        }
        if(list.size()>1) m = true;
        return m;
    }
    
    public static boolean isMove() {
        boolean m = false;
        boolean check = !v[0][0];
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                if(v[i][j]!=check) {
                    m |= bfs(i, j, check);
                }
            }
        }
        return m;
    }
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        v = new boolean[N][N];
        map = new int[N][N];
        min = Integer.parseInt(st.nextToken());
        max = 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 count = 0;
        while(isMove()) {
            count++;
        }
        System.out.println(count);
    }
}

코드에 대한 피드백이나 더 좋은 아이디어는 언제나 환영입니다.