[백준 16234] 인구 이동(Java)

문제 링크 : https://www.acmicpc.net/problem/16234

이 문제는 bfs를 이용하여 각 조건을 구현하면 됩니다.

bfs를 이용하여 인접한 칸이 L 이상 R 이하일 경우 큐에 추가하고, 연합에 속하게 된 칸의 좌표와, 인구수 그리고 칸의 개수를 재조정합니다. bfs가 한 번 끝날 경우 구한 값을 이용하여 칸의 좌표들을 모두 (연합의 인구수) / (연합을 이루고 있는 칸의 개수) 값으로 대체합니다. 이렇게 이동을 계속 하고 이동하지 않았을 경우에 지난 일 수를 리턴하여 값을 출력합니다.

다음은 코드입니다.

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

public class Main{
    static int N,L,R;
    static int res = 0;
    static int[][] req = new int[51][51];
    static int[] dx = {1,0,-1,0};
    static int[] dy = {0,1,0,-1};

    static boolean openGate(){
        boolean[][] check = new boolean[51][51];
        boolean isMoved = false;

        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(!check[i][j]){
                    // 국경선 공유 시작
                    check[i][j] = true;
                    Queue<Pair> queue = new LinkedList<>();
                    queue.add(new Pair(i,j));
                    // 연합에 속하게 된 칸 좌표
                    ArrayList<Pair> map = new ArrayList<>();
                    // 연합의 인구 수
                    int totalPopulation = 0;
                    // 연합을 이루고 있는 칸의 개수
                    int cnt = 0;

                    while(!queue.isEmpty()){
                        Pair pair = queue.poll();
                        int y = pair.y;
                        int x = pair.x;

                        // 연합 리스트에 추가
                        map.add(pair);
                        // 연합의 인구 수 더하기
                        totalPopulation += req[y][x];
                        // 연합을 이루고 있는 칸의 개수 카운트
                        cnt++;

                        for(int dir=0;dir<4;dir++){
                            int ny = y + dy[dir];
                            int nx = x + dx[dir];
                            if(ny<0 || ny>=N || nx<0 || nx>=N) continue;

                            // 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면 공유
                            if(!check[ny][nx]){
                                int diff = Math.abs(req[y][x] - req[ny][nx]);
                                if(diff>=L && diff<=R){
                                    isMoved = true;
                                    check[ny][nx] = true;
                                    queue.add(new Pair(ny,nx));
                                }
                            }
                        }
                    }

                    // (연합의 인구수) / (연합을 이루고 있는 칸의 개수) 값을 체크된 칸에 모두 넣기
                    int result = totalPopulation/cnt;
                    for(int idx=0;idx<map.size();idx++){
                        int y = map.get(idx).y;
                        int x = map.get(idx).x;
                        req[y][x] = result;
                    }
                }
            }
        }

        return isMoved;
    }

    static void movePopulation(int day){
        boolean isMoved = openGate();
        if(!isMoved) res = day;
        else movePopulation(day+1);
    }

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

        movePopulation(0);
        System.out.println(res);
    }
}


class Pair{
    int y;
    int x;

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

(+ 추가) 기존의 bfs 풀이 외에 dfs로 풀이도 가능합니다. 문제 특성 상 하나의 국가에 연결되어 있는 모든 국가를 탐색하여 값을 조정할 수 있기 때문에 dfs로 국가의 인구의 총합과 국가의 수를 구해 연결된 국가들을 같은 값으로 변경하는 방식으로 코드를 짤 수 있습니다.

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

class Main{
    static int N,L,R;
    static int[][] A;
    static boolean[][] check;
    static boolean isMove;
    static int[] dy = {1,0,-1,0}, dx = {0,1,0,-1};
    static ArrayList<Nation> arr;

    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());
        L = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());
        A = new int[N][N];

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

        int res = 0;
        while(true){
            isMove = false;
            check = new boolean[N][N];
            for(int i=0;i<N;i++){
                for(int j=0;j<N;j++){
                    if(!check[i][j]){
                        arr = new ArrayList<>();
                        int sum = open(new Nation(i,j,A[i][j]),A[i][j]);
                        int cnt = arr.size();
                        int val = sum/cnt;

                        if(cnt==1) continue;
                        for(int k=0;k<arr.size();k++){
                            Nation curr = arr.get(k);
                            A[curr.y][curr.x] = val;
                            isMove = true;
                        }
                    }
                }
            }

            if(!isMove) break;
            else res++;
        }
        System.out.println(res);
    }

    static int open(Nation curr, int sum){
        check[curr.y][curr.x] = true;
        arr.add(curr);

        int tmp = 0;
        for(int i=0;i<4;i++){
            int ny = curr.y + dy[i];
            int nx = curr.x + dx[i];
            if(ny<0 || ny>=N || nx<0 || nx>=N) continue;

            if(!check[ny][nx]){
                int diff = Math.abs(A[ny][nx] - A[curr.y][curr.x]);
                if(diff >= L && diff <= R){
                    tmp += open(new Nation(ny,nx,A[ny][nx]),A[ny][nx]);
                }
            }
        }
        return tmp+sum;
    }

    static class Nation{
        int y;
        int x;
        int pop;

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