백준 16234 인구이동 java

2018년 10월 21일 삼성 SW 테스트 2번 문제 : 인구 이동 (백준 16234 번)

문제 

N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다.

오늘부터 인구 이동이 시작되는 날이다.

인구 이동은 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.

• 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루동안 연다.
• 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.
• 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.
• 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.
• 연합을 해체하고, 모든 국경선을 닫는다.

각 나라의 인구수가 주어졌을 때, 인구 이동이 몇 번 발생하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N, L, R이 주어진다. (1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100)

둘째 줄부터 N개의 줄에 각 나라의 인구수가 주어진다. r행 c열에 주어지는 정수는 A[r][c]의 값이다. (1 ≤ A[r][c] ≤ 100)

출력

인구 이동이 몇 번 발생하는지 첫째 줄에 출력한다.

해결방법

1.  DFS 로 전체 map 리스트에서 방문하지 않은 곳부터 시작해서 조건에 맞는 (차이가 L <= x <=R) 인 곳 리스트에 담기.

2. DFS 탐색 끝난 후 리스트 갯수 확인하여 변동이 생겼을 경우(조건에 맞는 데이터가 있을 경우), map 데이터 평균 값으로 수정.

3. 모두 방문했을 경우, 방문여부 확인하는 배열 초기화 후 인구이동이 필요한지 다시 확인. 

   필요할 경우 (시간 + 1초) 해준 후 1번부터 다시 실행.

java 코드

import java.util.*;
public class Algo_16234 {
    
    static int n;
    static int L;
    static int R;
    static int map[][];
    static boolean visited[][];
    
    static int dx[] = {1,-1,0,0};
    static int dy[] = {0,0,1,-1};
    
    public static void main(String [] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        L = sc.nextInt();
        R = sc.nextInt();
        int sec = 0;
        map = new int[n][n];
        
        
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                map[i][j]=sc.nextInt();
            }
        }
        
        while(true){
            visited = new boolean[n][n]; // 방문 초기화
            if(!check()){
                sec++;  // 인구이동이 또 필요한 경우
            } else {
                break; 
            }
        }
        
        System.out.println(sec);
        
    }
    
    // 인구 이동 필요한지 전체 지도 확인.
    public static boolean check(){
        List<Node> n_list;
        boolean isDone = true;  // 이동이 더이상 필요하지 않을 경우 true. 필요한 경우 false
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                // 방문하지 않은 경우
                if(!visited[i][j]){
                    n_list = new LinkedList<>();
                    n_list.add(new Node(i,j));
                    // sum - 리스트에 저장된 값의 합.
                    int sum = dfs(i,j,n_list,0);
                    if(n_list.size() > 1){ // 리스트 크기가 1 이상일 경우(= 인구이동이 필요한 데이터가 있을경우)
                        change(sum,n_list); // 평균값 계산해서 map 갱신.
                        isDone= false; 
                    }
                }
            }
        }
        return isDone;
    }
    
    // 평균값으로 map 갱신.
    public static void change(int sum,List<Node> n_list){
        int avg = sum/n_list.size();
        for(Node node:n_list){
            map[node.x][node.y] = avg;
        }
    }
    
    
    public static int dfs(int x, int y, List<Node> n_list, int sum){
        visited[x][y] =true;
        sum= map[x][y];
        
        for(int i=0;i<4;i++){
            int next_x = x+dx[i];
            int next_y = y+dy[i];
            
            if(next_x < 0 || next_x >=n || next_y <0 || next_y >=n ){
                continue;
            }
            if(!visited[next_x][next_y]){
                int d = Math.abs(map[x][y] - map[next_x][next_y]);
                if(d >= L && d <= R){
                    n_list.add(new Node(next_x,next_y));
                    sum+= dfs(next_x,next_y,n_list,sum);
                }
            }
        }
        return sum;
    }    
    
}
class Node{
    int x;
    int y;
    public Node(int x, int y){
        this.x = x;
        this.y = y;
    }
}