[백준] BOJ - 16234 인구 이동 자바 java(골드5)

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

16234번: 인구 이동

 

 

1. 나의풀이

      

      

      

    
    

      <bash />
    
import java.util.*;
import java.io.*;
public class Main {
    static int n=0;
    static int left, right;
    static int[] dx={0,0,-1,1};
    static int[] dy={-1,1,0,0};
    static int[][] map;
    static boolean[][] visited;
    static int[][] unitedFlag;
    static boolean end= true;
    
    public static class Node{
        int x, y, people, kan;
        public Node(){}
        public Node(int x, int y, int people, int kan){
            this.x=x;
            this.y=y;
            this.people=people;
            this.kan= kan;
        }
    }
    
    public static Node bfs(int x, int y, int people, int kan, int united){
        Queue<Node> q= new LinkedList<>();
        Node now = new Node(x, y, people, kan);
        q.offer(now);
        visited[x][y]=true;
        unitedFlag[x][y]=united;
        int hap=people;
        int cnt=kan;
        while(!q.isEmpty()){
            now= q.poll();
            //4방향
            for(int i=0;i<4; i++){
                int nextX=now.x+dx[i];
                int nextY=now.y+dy[i];

                if(nextX<0 || nextY<0 || nextX>= n || nextY >= n){
                    continue;
                }
                

                if(visited[nextX][nextY]==true){
                    continue;
                }

                if(Math.abs(map[nextX][nextY] - map[now.x][now.y])>=left && Math.abs(map[nextX][nextY] - map[now.x][now.y])<=right){
                    end=true; //하나라도 국경이 열렸다는 표시 
                    visited[nextX][nextY]=true;
                    unitedFlag[nextX][nextY]=united;
                    hap+=map[nextX][nextY];
                    cnt++;
                    q.offer(new Node(nextX, nextY, hap, cnt));

                }
            }
        }
        return now;
    }
    
    public static void move(int united, int val){
        for(int i=0; i<n; i++){
            for(int j=0;j<n; j++){
                if(unitedFlag[i][j] == united){
                    map[i][j]=val;
                }
            }
        }
        
    }
    
    public static void main(String args[]) throws Exception{
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw= new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        n = Integer.parseInt(st.nextToken());
        left = Integer.parseInt(st.nextToken());
        right = Integer.parseInt(st.nextToken());
        
        map= new int[n][n];
        visited= new boolean[n][n];
        unitedFlag=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());
            }
        }
        int answer=0;
        int united=1;
        //국경이 닫힐때까지 반복 
        while(end == true){
            end=false;
            visited= new boolean[n][n];//방문여부 초기화
            
            for(int i=0; i<n; i++){
                for(int j=0; j<n; j++){
                    if(visited[i][j] == false){//하나의 연합 시작
                        Node node=bfs(i, j, map[i][j], 1, united);
                        move(united, (int)(node.people/node.kan));//인구이동 
                        united++;
                    }
                }
            }
            
            if(end == true){//인구 이동이 발생했다
                answer++;
            }
        }
        bw.write(Integer.toString(answer));
        bw.flush();
        br.close();
        bw.close();
    }
}