[백준][Java] - G4_16234_인구이동

https://www.acmicpc.net/problem/16234

16234번: 인구 이동

🌿 - 문제 설명

📌- 풀이

 

N의 최대치가 50이라 많아봤자 2500개의 도시만 있으므로 BFS를 통해서 탐색해도 시간초과가 나오지 않을 거라 생각해서 BFS로 풀었다.

1. BFS로 탐색하면서 주변의 도시들이 L이상 R이하인지 탐색

2. L이상 R이하라면 큐에 추가해서 연합된 도시를 형성

3. 큐에 추가된 도시들의 수와 합을 구함 -> 평균을 구함

4. 연합된 각각의 도시들의 인구 이동한 값으로 교체

5. 더이상 근처 도시와 연합할 수 없을때까지 반복

 

결과값 출력!

 

 

아쉬운 부분은 큐를 2개 사용해서 메모리 사용이 조금이나마 많아졌다는 점

더 쉽고 간단하게 짤 수 있는 방법도 있겠지만, 최대한 머리에서 생각나는대로 바로 짜봤다.

다른 문제들을 많이 풀어보면서 더 보완하도록 해야겠다.

 

🔥 - Java 전체 코드

 

package BFS.G4_16234_인구이동;

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

public class Main {
        public static int N,L,R,result = -1;
        static int[][] arr;
        static boolean[][] visited;
        static int[] dx={0,0,1,-1};
        static int[] dy={1,-1,0,0};

    public static void main(String[] args) throws IOException {
        //BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedReader br = new BufferedReader(new FileReader("src/input.txt"));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());

        arr = new int[N][N];

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

        int set = 0;
        while(set != N*N){ // 도시가 BFS를 통해 연합되는 곳 없이 전부 탐색을 하게 된다면 끝난 것이므로 조건을 N*N이 아닐 때까지만 반복문을 실행함
            set =0;
            visited = new boolean[N][N]; // 계속해서 방문체크를 하기 위해 초기화
            for(int i=0;i<N;i++){
                for(int j =0;j<N;j++){
                    if(!visited[i][j]){
                        BFS(i,j);
                        set++;
                    }
                }
            }
            result++;


        }
        System.out.println(result);
    }

    public static void BFS(int x, int y){
        visited[x][y] = true;
        Queue<City> que = new LinkedList<>(); // avg를 탐색하기 위한 큐
        Queue<City> cityList = new LinkedList<>(); // 연합된 도시들을 저장해서 평균 값(avg)로 초기화 하기 위함
        que.add(new City(x,y));
        cityList.add(new City(x, y));
        int sum =arr[x][y]; // 연합된 도시들의 합
        int count =1; // 연합된 도시의 수
        while(!que.isEmpty()){
            City ct = que.poll();

            for(int i =0;i<4;i++){
                int nx = ct.x +dx[i];
                int ny = ct.y +dy[i];

                if(nx>=0 && nx<N && ny>=0 && ny<N && !visited[nx][ny]){
                    int dif = Math.abs(arr[nx][ny]-arr[ct.x][ct.y]);
                    if( dif >= L && dif <= R){ // 차이가 L이상 R이하
                        que.add(new City(nx,ny));
                        cityList.add(new City(nx,ny));
                        visited[nx][ny] = true;
                        count++;
                        sum += arr[nx][ny];
                    }
                }
            }
        }
        int avg = sum/count;

        while (!cityList.isEmpty()) { // 연합된 도시들의 값을 평균값으로 바꾸기 위함
            City ct = cityList.poll();
            arr[ct.x][ct.y] = avg;
        }


    }

}


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