[백준] 16234번 인구 이동 풀어보기 [Java]

구현과 BFS문제이다. 두 문제 연속으로 한번에 맞춰서 기분이 좋다. 하지만, 효율성이 극악인거 같다,,,,좀 더 효율이 어떻게 좋게 만들지 고민을 해야겠다!!

 

👨‍🏫 풀이

어느 나라가 국경을 서로 여는지 알기 위해서, BFS로 현재 연 국경에 대해서 모두 구했다. 그래서 국경을 연 나라끼리는 동일한 숫자를 저장해줬다.

서로 국경을 연 나라를 조각으로 봤다.

그리고 조각에는 국경을 연 나라들의 인구수 합과 나라 갯수를 저장했다.

조각들의 갯수가 N*N이라면, 모든 나라가 국경을 연 것이 아니기 때문에 시뮬레이션을 끝냈고, 그렇지 않다면, 저장한 조각들의 나라들에게 인구수의 합 / 나라 갯수를 해줘서 저장을 해줬다.

조각들의 갯수가 N*N이 될때까지 계속 해주었다.

 

👨🏻‍💻 코드

package 번16234;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static class Node{
        int x,y;
        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    static class Country{
        int cnt;
        int sum;
        int num;

        public Country(int cnt, int sum, int num) {
            this.cnt = cnt;
            this.sum = sum;
            this.num = num;
        }
    }
    static int N,L,R;
    static int[][] map;
    static int[][] tmp;
    static int[] mX = {0,0,1,-1};
    static int[] mY = {1,-1,0,0};
    static Queue<Country> moveCountry = new LinkedList<Country>();
    public static void main(String[] args) throws IOException {
        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());

        map = new int[N][N];
        tmp = new int[N][N];
        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 ans = 0;
        while(true) {
            int cnt = 1;

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (tmp[i][j] == 0) {
                        bfs(cnt, i, j);
                        cnt++;
                    }
                }
            }
            if(cnt == N*N + 1) break;
            move();
            ans++;
        }

        System.out.println(ans);
    }

    private static void move() {
        while(!moveCountry.isEmpty()) {
            Country cur = moveCountry.poll();
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if(tmp[i][j] == cur.num) {
                        map[i][j] = cur.sum / cur.cnt;
                        tmp[i][j] = 0;
                    }
                }
            }
        }
    }

    private static void bfs(int num, int i, int j) {
        Queue<Node> q = new LinkedList<>();
        tmp[i][j] = num;
        int sum = 0;
        int cnt = 0;
        q.add(new Node(i,j));
        while(!q.isEmpty()){
            Node cur = q.poll();
            sum += map[cur.x][cur.y];
            cnt++;
            for(int k = 0 ; k < 4 ; k++){
                int nX = cur.x + mX[k] ; int nY = cur.y + mY[k];
                if(nX < 0 || nX >= N || nY < 0 || nY >= N) continue;
                if(tmp[nX][nY] != 0) continue;
                int diff = Math.abs(map[cur.x][cur.y] - map[nX][nY]);
                if( diff >= L && diff <= R){
                    tmp[nX][nY] = num;
                    q.add(new Node(nX,nY));
                }

            }
        }
        moveCountry.add(new Country(cnt,sum,num));
    }
}