[BOJ]16234번: 인구 이동

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

16234번: 인구 이동

 

 

알고리즘 분류

• 구현
• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 시뮬레이션

문제 설명

내가 파악한 문제의 요지는 다음과 같다

1. 각 칸이 하나의 국가이고 인접한 국가끼리의 인구수 차이가 L과 R 범위 내라면 국경을 열어 인구 이동을 시작한다.

2. 인구 이동 후 각 칸의 인구수는 (연합의 인구수) / (같은 연합의 수)이다. (여기서 같은 연합의 수 라고 표현한 것은 다수의 연합이 발생할 수 있기 때문)

3. 위의 싸이클을 돈 다음엔 인구 이동이 없을 때까지 반복한다.

4. 최대 2000번까지의 인구 이동이 일어나는 입력만 주어진다.

 

문제 해결은 FindUnion() => BorderOpen() => 인구수 재계산의 흐름으로 구현하였다.

다수의 연합이 발생 했을 경우를 어떻게 처리할지 고민을 많이 했는데 다른 분의 코드를 참조하여 Union Queue를 활용하여 해결

import java.util.*;

public class Main {
  
    static int N,L,R;
    static int[] dx = {-1,1,0,0};   // up , down, left,right;
    static int[] dy = {0,0,-1,1};   // up , down, left,right;
    static int[][] map;
    static boolean[][] border;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        N = sc.nextInt();
        L = sc.nextInt();
        R = sc.nextInt();
        
        map = new int[N][N];
        
        for(int r=0;r<N;r++)
        {
            for(int c=0;c<N;c++)
            {
                map[r][c] = sc.nextInt();
            }
        }
        
        PrintArray();
        System.out.println(FindUnion());        
        sc.close();
    }    
    
    private static int FindUnion()
    {
        int answer =0;        
        while(true)
        {
            border = new boolean[N][N];
            boolean init = false;
            
            for(int row = 0; row<N; row++) 
            {
                for(int col = 0; col<N;col++) 
                {
                   if(border[row][col])
                   {
                       continue;
                   }
                   if(BorderOpen(row,col)) {
                       init = true;
                   }
                }
            }            
            if(init) answer++;
            else return Math.min(2000,answer);            
        }        
    }


    private static boolean BorderOpen(int r, int c)
    {
        Queue<Point> q     = new LinkedList<Point>();
        Queue<Point> union = new LinkedList<Point>();
        
        q.add(new Point(r,c));
        union.add(new Point(r,c)); //시작점부터 연합을 찾는거니까 추가해줌
        
        border[r][c] = true;
        
        int sum = map[r][c];
        
        while(!q.isEmpty())
        {
            int size = q.size();
            
            for(int sz =0; sz<size;sz++)
            {
                Point p = q.poll();
                int x = p.x;
                int y = p.y;
                
                for(int cycle = 0; cycle<4;cycle++)
                {
                    int cx = x+dx[cycle];
                    int cy = y+dy[cycle];
                    
                    if(0<=cx && cx<N && 0<=cy && cy <N && !border[cx][cy])
                    {
                        int diff = Math.abs(map[x][y]-map[cx][cy]);
                        if(L<=diff && diff <=R) {
                            sum+=map[cx][cy];
                            border[cx][cy] = true;
                            q.add(new Point(cx,cy));
                            union.add(new Point(cx,cy));
                        }
                    }                         
                }
            }
        }
        
        if(union.size() == 1) return false;
        else 
        {
          int redis = sum / union.size();          
          for(Point p : union) 
          {
              map[p.x][p.y] = redis;
          }
        }
        return true;
    }
    private static void PrintArray() 
    {        
        for(int row = 0; row<N; row++) 
        {
            for(int col = 0; col<N;col++) 
            {
                System.out.printf("%3d ",map[row][col]);
            }
            System.out.println("");
        }        
    }
}

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