<Algorithm> 136. 인구이동(BJO)

1. 16234번 인구이동(BJO)

• DFS 활용문제

• 2018년 하반기 삼성 코테에 나왔던 문제 유형이다. 그때도 테케까지 풀긴했지만 뒤에서 시간초과가 생겼을것이라 생각한다.

• DFS와 비트연산을 이용해 풀었는데 생각보다 속도가 느리다. 시간초과는 나지 않았지만 속도를 줄일 방법을 찾아봐야겠다.

import java.util.Scanner;
 
public class Main {
    static int[][] arr;
    static int[][] wall;
    static int n;
    static int l;
    static int r;
    static int[] dx = {-1,0,1,0}; // 시계방향
    static int[] dy = {0,1,0,-1};
    static boolean[][] visited;
    static boolean[][] visited2;
    static int total;
    static int cnt;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        l = sc.nextInt();
        r = sc.nextInt();
        arr = new int[n][n];
        wall = new int[n][n];
        visited = new boolean[n][n];
        visited2 = new boolean[n][n];
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                arr[i][j] = sc.nextInt();
            }
        }
        /******************************
         * DFS와 비트연산을 이용하여 
         * 먼저 통로를 만들어서 길을 만들고
         * DFS를 통해 탐색하여 인구수를 바꿔준다.
         * 위를 반복하여 더이상 통로를 만들 수 없을
         * 경우 답을 출력한다.  
         *******************************/
        
      int move = 0;
      while(wallCheck()) {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(!visited[i][j]) {
                    visited[i][j] = true;
                    visited2 = new boolean[n][n];
                    total = arr[i][j];
                    cnt = 1;
                    dfs(i, j);
                    if(cnt > 1) {
                        arr[i][j] = total/cnt;
                        dfs_modify(i, j, total/cnt);
                    }
                }
            }
         }
        move++;
        /*System.out.println(move+"초 시간");
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                System.out.print(arr[i][j]+"  ");
            }
            System.out.println();
        }*/
        
        visited = new boolean[n][n];
        wall = new int[n][n];
      }
      System.out.println(move);
    }
    
    public static void dfs(int i, int j) {
        
        for(int k = 0; k < 4; k++) {
            int dir = 1<<k;
            int nx = i + dx[k];
            int ny = j + dy[k];
            if(nx>=0 && ny>=0 && nx<n && ny<n && (wall[i][j]&dir)==dir && !visited[nx][ny]) {
                visited[nx][ny] = true;
                visited2[nx][ny] = true;
                total += arr[nx][ny];
                cnt ++;
                dfs(nx, ny);
            }
        }
        
    }
    public static void dfs_modify(int i,int j,int people) {
        /*for(int k = 0; k < 4; k++) {
            int nx = i + dx[k];
            int ny = j + dy[k];
            if(nx>=0 && ny>=0 && nx<n && ny<n && visited2[nx][ny]) {
                visited2[nx][ny] = false;
                arr[nx][ny] = people; 
                dfs_modify(nx, ny, people);
            }
        }*/
        for(int x = 0; x < n; x++) {
            for(int y = 0; y < n; y++) {
                if(visited2[x][y]) {
                    visited2[x][y] = false;
                    arr[x][y] = people; 
                }
            }
        }
        
    }
    
    
    public static boolean wallCheck() {
        boolean hasWall = false;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                int people = arr[i][j];
                for(int k = 0; k < 4; k++) {
                    int dir = 1<<k;
                    int nx = i + dx[k];
                    int ny = j + dy[k];
                    if(nx>=0 && ny>=0 && nx<n && ny<n) {
                        int diff = Math.abs(people-arr[nx][ny]);
                        if(diff >=l && diff <= r) {
                            hasWall = true;
                            wall[i][j]+=dir;
                        }
                    }
                }
            }
        }
        return hasWall;
    }
}
 

다른 방법 풀이 PS. 04/11

• 시간이 짧은 코드들을 보면서 그룹을 만들어서 DFS로 처리하면 위의 코드처럼 불필요한 반복을 줄일 수 있는 것을 알게 되었다.

• 최대 n*n 모든 나라에 해당하는 1차원배열의 방을 만든다. 그리고 DFS 탐색을 통해 국경열린 나라에 대한 그룹을 지어준다.

• 그룹 표시가 끝나면 인구를 업데이트 해주는데 이때 모든 방을 돌면서 아까 그룹에 해당하는 인구수를 부여한다. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main2 {
    static int[][] arr;
    static int n;
    static int l;
    static int r;
    static int[] dx = {-1,0,1,0}; // 시계방향
    static int[] dy = {0,1,0,-1};
    static int[][] groupNumber;
    static int[] population;
    static int total;
    static int cnt;
    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());
        arr = new int[n][n];
        groupNumber = new int[n][n];
        population = new int[n*n+1];
        
        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());
            }
        }
        moveCnt = 0;
        solve();
        System.out.println(moveCnt);
    }
    static int moveCnt;
    private static void solve() {
        while (true) {
            int group = 1;
            boolean ck = false;
            for(int i = 0; i<n; i++) {
                for(int j = 0; j<n; j++){
                    if(groupNumber[i][j]==0) {
                        cnt = 0;
                        dfs(i, j, group);
                        if(cnt>1) {
                            population[group] = population[group]/cnt;
                            ck = true;
                        }
                        group++;
                    }
                }
            }
            if(!ck) return;
            move();
            groupNumber = new int[n][n];
            population = new int[n*n+1];
            moveCnt++;
        }
    }
    private static void move() {
        for(int i = 0; i<n; i++) {
            for(int j = 0; j<n; j++){
                arr[i][j] = population[groupNumber[i][j]];
            }
        }
    }
    
    private static void dfs(int x,int y,int group) {
        groupNumber[x][y] = group;
        population[group]+= arr[x][y];
        cnt++;
        
        for(int i = 0; i < 4; i++) {
            int nx = x+dx[i];
            int ny = y+dy[i];
            int size = arr[x][y];
            
            if(isBoundary(nx, ny)&&groupNumber[nx][ny]==0&&isOpen(size, arr[nx][ny])) {
                dfs(nx, ny, group);
            }
        }
        
    }
    private static boolean isOpen(int size, int target) {
        int calc = Math.abs(size - target);
        if(calc < l || calc>r) return false;
        return true;
    }
    private static boolean isBoundary(int nx,int ny) {
        if(nx<0 || ny<0 || nx>=n || ny>=n )
            return false;
        return true;
    }
    
}