[beakjoon]16234 인구 이동

이전의 풀이보다 훨씬 깔끔하게 푼 거 같아서 추가 포스팅.

이번 풀이의 포인트는 인접한 나라를 관리할 때, 여기저기 변수 만들기가 헷갈리기도 하고 구역만 정해지면 독립적이라고 생각이 들어서 인접한 나라들을 다른 Queue에 넣어주었다. (Queue<Dot> resultQueue)

Queue에 넣어주면서 합계도 한 번에 하였고, Queue에 하나밖에 없으면 계산할 필요가 없기에 return 처리해 주었더니 이전 풀이에 비해 속도가 상당히 빨라졌다. 메모리는 똑같이 소모되는데 재탐색하는 과정이 없어서인듯하다.

풀이 방식을 정리하자면 일단 인접한 나라들을 전부 파악하며 두 나라들의 인구 차 범위를 확인해준다. (BFS, DFS 상관없음)

요구된 범위 안에 들어가 있다면, 다른 Queue에 넣어준다. 여기에 나는 flag를 주어서 인구 이동할 수 있음을 확인해주었다.

이를 이용해서 분배될 인구 값을 구해서 다시 넣어준다.

요구된 범위 안에 없을 때까지 계속 확인한다.

 

 

//https://www.acmicpc.net/problem/16234
import java.io.*;
import java.util.*;
 
/**
 * 인접한 나라는 국경선을 공유하는 나라.
 **/
class Main {
    static int N, L, R;
    static int[][] dirs = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
    static int[][] map;
    static boolean isPossible = true;
    static boolean[][] marked;
 
    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());
        R = Integer.parseInt(st.nextToken());
        
        map = new int[N][N];
        marked = new boolean[N][N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                int cur = Integer.parseInt(st.nextToken());
                map[i][j] = cur;//
            }
        }
        int days = 0;
        while(true) {
            isPossible = false;
            marked = new boolean[N][N];
            
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if(marked[i][j]) continue;
                    //해당하는 애들만 싹다 따로 모아서 미리 넣어주자....
                    nearCountry(new Dot(i, j));
                }
            }
            if(!isPossible) break;
            days++;
            
        }
        
        System.out.println(days);
    }
 
    public static void nearCountry(Dot cur) {
        Queue<Dot> queue = new LinkedList<>();
        Queue<Dot> resultQueue = new LinkedList<>();
        queue.add(cur);
        resultQueue.add(cur);
        marked[cur.row][cur.col] = true;
        int sum = map[cur.row][cur.col];
        
        while (!queue.isEmpty()) {
 
            Dot dot = queue.poll();
            for (int i = 0; i < 4; i++) {
                int nextR = dot.row + dirs[i][0];
                int nextC = dot.col + dirs[i][1];
 
                if (nextR < 0 || nextC < 0 || nextR >= N || nextC >= N)
                    continue;
                if (marked[nextR][nextC])
                    continue;
                int sub = Math.abs(map[dot.row][dot.col] - map[nextR][nextC]);
                if (sub < L || sub > R)
                    continue;
        
                isPossible = true;
                sum += map[nextR][nextC];
                resultQueue.add(new Dot(nextR, nextC));
                queue.add(new Dot(nextR, nextC));
                marked[nextR][nextC] = true;
            }
        }
        
        sum /= resultQueue.size();
        if (resultQueue.size() == 1)
            return;
        
        while (!resultQueue.isEmpty()) {
            Dot dot = resultQueue.poll();
            map[dot.row][dot.col] = sum;
        }
    }
}
 
class Dot {
    int row;
    int col;
 
    Dot(int row, int col) {
        this.row = row;
        this.col = col;
    }
}