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

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

출처 : 링크

2018년 하반기 삼성 코테 기출이다.

DFS와 BFS 모두 사용이 가능하고, 인구 이동이 가능할 때까지 계속 진행해서 횟수를 출력해주면 된다.

이동이 가능한 배열마다 같은 숫자를 저장하도록 2차원 배열을 하나 더 만들었다. (copymap)

DFS를 통해 조건에 맞는 이동가능 배열끼리 묶어주고, 해당 map의 값을 모두 더해 평균을 내서 저장시켰다.

평균을 구하는 반복문을 따로 만들어서 사용하면 시간초과로 풀 수 없으므로 먼저 리스트를 생성해 DFS를 호출하는 반복문 안에서 평균 값 계산을 같이 해야 시간을 줄일 수 있었다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
 
    static class C {
        int y;
        int x;
 
        C(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }
 
    static int N, L, R;
    static int[][] map;
    static int[][] copymap;
    static boolean[][] visited;
 
    static int[] dy = { 0, 0, -1, 1 };
    static int[] dx = { -1, 1, 0, 0 };
    static int c;
    static int result = 0;
    static int sum, cnt;
    static ArrayList<int[]> 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());
 
        map = 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());
            }
        }
 
        while (true) {
            
            copymap = new int[N][N];
            visited = new boolean[N][N];
            
            c = 1;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (copymap[i][j] == 0) {
                        arr = new ArrayList<>();
                        sum = map[i][j];
                        arr.add(new int[]{i,j});
                        cnt = 1;
                        
                        dfs(i, j);
                        c++;
                        
                        if(cnt > 1){
                            for (int t = 0; t < arr.size(); t++) {
                                map[arr.get(t)[0]][arr.get(t)[1]] = sum / cnt;
                            }
                        }
                    }
                }
            }
 
            int[] cnt = new int[--c];
 
            if (cnt.length == N * N) {
                break;
            }
            
            
            result++;
 
        }
        System.out.println(result);
    }
 
    public static void dfs(int y, int x) {
 
        copymap[y][x] = c;
        visited[y][x] = true;
 
        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
 
            if (ny >= 0 && nx >= 0 && ny < N && nx < N) {
                int k = Math.abs(map[y][x] - map[ny][nx]);
                if (k >= L && k <= R && !visited[ny][nx]) {
                    
                    cnt++;
                    sum += map[ny][nx];
                    arr.add(new int[]{ny,nx});
                    dfs(ny, nx);
                }
            }
        }
    }
    
    public static void bfs(int y, int x) {
        
        Queue<C> q = new LinkedList<>();
        C cc = new C(y,x);
        q.add(cc);
        
        while(!q.isEmpty()){
            
            C c1 = q.poll();
            copymap[c1.y][c1.x] = c;
            //sum += map[c1.y][c1.x];
            visited[c1.y][c1.x] = true;
            
            for (int i = 0; i < 4; i++) {
                int ny = c1.y + dy[i];
                int nx = c1.x + dx[i];
 
                if (ny >= 0 && nx >= 0 && ny < N && nx < N) {
                    int k = Math.abs(map[c1.y][c1.x] - map[ny][nx]);
                    if (k >= L && k <= R && !visited[ny][nx]) {
                        q.add(new C(ny,nx));
                        visited[ny][nx] = true;
                    }
                }
            }
            
        }
    }
 
}