[백준 3주차 - 16234] 인구이동 (Java)

📌 문제

 

 

📝풀이과정

인구이동이 없을 때까지 모든 좌표를 DFS로 탐색하면서  while문으로 반복하였고, 인구인동이 없으면 break문으로 종료하도록 코드를 구현하였다

 

- 두 나라의 인구 차이 L이상 R이하 일 때 탐색한다

- ArrayList를 사용하여 방문한 좌표값을 저장한다

- DFS 탐색이 끝난 후, (ArrayList의 합)/ (ArrayList의 사이즈) 를 각 칸의 인구수로 만든다

- 인구 이동이 없으면 break문으로 종료함

while(){ 
	for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                dfs(i,j) //간격이 l이상 r이하이면 탐색
            }
    }
    
    ...
    
    if(flag==false) break; //인구이동 발생 안하면 끝
}

 

💻코드

import java.util.Scanner;
import java.io.*;
import java.util.*;

public class Main{
	static int n,l,r;
	static int map[][];
	static int visited[][];
	static int dy[]={-1,0,1,0};
	static int dx[]={0,1,0,-1};
	static int sum=0;
	static ArrayList<Pair> list=new ArrayList<>();
	
	public static class Pair{
		int y,x;
		Pair(int y,int x){
			this.y=y;
			this.x=x;
		}
	}
	public static void dfs(int y,int x){
		for(int i=0;i<4;i++){
			int ny=y+dy[i];
			int nx=x+dx[i];
			if(ny<0 || ny>=n || nx<0 || nx>=n) continue;
			if(visited[ny][nx]==0 && Math.abs(map[y][x] - map[ny][nx])>=l && Math.abs(map[y][x]- map[ny][nx])<=r ){
				visited[ny][nx]=1;
				list.add(new Pair(ny,nx));
				sum+=map[ny][nx];
				dfs(ny,nx);
			}
		}
	}
    public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		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];
		visited=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 cnt=0;
		
		while(true){
			boolean flag=false;
			//초기화
			for(int i=0;i<n;i++){
				Arrays.fill(visited[i],0);
			}
			for(int i=0;i<n;i++){
				for(int j=0;j<n;j++){
					if(visited[i][j]==0){
						list.clear();
						visited[i][j]=1;
						list.add(new Pair(i,j));
						sum=map[i][j];
						dfs(i,j);
						if(list.size()==1) continue;
						for(Pair p :list){
							map[p.y][p.x]=sum/list.size();
							flag=true;
						}
					}
				}
			}
			if(flag==false) break;
			cnt++;
			
		}
		System.out.println(cnt);
    }
}