[backjoon]16234 인구 이동 java

16234번: 인구 이동

16234번: 인구 이동

좀더 간결하게 풀이해서 포스팅 (링크)
이전엔 방문체크를 다른 배열을 둬서 했는데 그런 것 없이 한번에 풀이하여서 좀더 깔끔한 풀이가 됨

풀이 개요

BFS나 DFS 와 같이 완전 탐색 이용해서 풀이하면 되는 문제.
나는 BFS를 사용하였고, BFS 두 번 돌리면 시간 초과가 일어나기에 한번 BFS를 돌릴 때, 인구 이동시 필요한 값들을 다 저장해야한다.
문제 풀이시 약간 헷갈려서 같은 역할을 하는 방문 체크를 위한 배열이 2개 있었는데 이 문제로 시간 초과도 떴다.
불필요한 부분은 제외하고 면밀한 풀이가 필수!

 

import java.io.*;
import java.util.*;
 
class Main {
    static int N, L, R, marking;
    static boolean flag;
    static int[][] map , stamp;
    static boolean[][] marked;
    static ArrayList<Dot>[] arr;
    static int[] sum;
    static int max = 50 * 50 +1;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken()); // min
        R = Integer.parseInt(st.nextToken()); // max
 
        map = new int[N + 1][N + 1];
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                int temp = Integer.parseInt(st.nextToken());
                map[i][j] = temp;
            }
        }
        int answer = 0;
 
        while (true) {
            marked = new boolean[N + 1][N + 1]; // 재탐색 안 하기 위함.
            flag = false;
            marking = 0;
            arr = new ArrayList[max];
            sum = new int[max];
            for(int i = 0; i < max; i++) {
                arr[i] = new ArrayList<>();
            }
            //국경 확인 -> 전체를 확인하면서 국경을 파악한다. -> stamp를 남겨서 그룹화함.
            stamp = new int[N][N];
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if(marked[i][j]) continue;
                    boundary(new Dot(i, j));
                    marked[i][j] = true;
                }
            }
 
            if(!flag) break;
            answer++;
            //인구 이동
            move();
        }
        System.out.println(answer);
    }
 
    public static void move() {
        for(int i = 0; i < max; i++) {
            ArrayList<Dot> list = arr[i];
            if(list.size() == 0) continue;
            int totalSum = sum[i];
            int cal = totalSum/list.size();
            for(Dot d : list) {
                map[d.row][d.col] = cal;
            }
        }
 
    }
    public static void boundary(Dot d) {
        Queue<Dot> queue = new LinkedList<Dot>();
 
        int[][] dirs = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
        queue.add(d);
        marked[d.row][d.col] = true;
        stamp[d.row][d.col] = ++marking;
        arr[stamp[d.row][d.col]].add(d);
        sum[stamp[d.row][d.col]] += map[d.row][d.col];
        while (!queue.isEmpty()) {
            Dot cur = queue.poll();
 
            for (int dir = 0; dir < 4; dir++) {
                int nextR = cur.row + dirs[dir][0];
                int nextC = cur.col + dirs[dir][1];
 
                if (nextR < 0 || nextC < 0 || nextR >= N || nextC >= N)
                    continue;
                if (marked[nextR][nextC])
                    continue;
 
                int cal = Math.abs(map[cur.row][cur.col] - map[nextR][nextC]);
 
                if (cal < L || cal > R)
                    continue;
 
                marked[nextR][nextC] = true;
                marked[nextR][nextC] = true;
                queue.add(new Dot(nextR, nextC));
                arr[stamp[d.row][d.col]].add(new Dot(nextR, nextC));
                sum[stamp[d.row][d.col]] += map[nextR][nextC];
                flag = true;
            }
        }
    }
}
class Dot{
    int row;
    int col;
    Dot(int row, int col){
        this.row = row;
        this.col = col;
    }
}