[ 백준 ][ 자바][ 16234 ] 인구이동

어라 티스토리 에디터가 변경됬다..

오 글씨체 이뻐이뻐

깔끔한게 이쁘다. 나중에 내 블로그 만들때 좀 참고해야겠다.

오랜만에 포스팅...

그말인 즉슨...나태했다는 의미다.

제일 중요한때 인데...뭐하는지...

여튼..이 문제는 조금 해맸다

예제만 보고 진행했다가 값이 안나와서 뭔가 싶었는데

연합은 딱 하나가 아닐수도 있다는것...고립되어있는 연합을 생각해줘야한다.

이거떄문에 해맸는데 나머지는 그냥 dfs다.

지금까지 본 삼성문제중엔 가장 쉬운거같다.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Land{
	int y;
	int x;
	Land(int y, int x){
		this.y = y;
		this.x = x;
	}
}
public class Main_backjoon_16234_인구이동 {
	static int N;
	static int L;
	static int R;
	static int[][] MAP = new int[101][101];
	static boolean[][] visited = new boolean[101][101];
	static Queue q = new LinkedList();
	static ArrayList openList = new ArrayList();
	static int[] dx = {1, -1, 0, 0 };
	static int[] dy = {0, 0, 1, -1}; 
	static int CNT = 0;
	static boolean isPossible;
	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());
	
		for(int i = 0 ; i < N ; i++) {
			st = new StringTokenizer(br.readLine() , " ");
			int idx = 0;
			while(st.hasMoreTokens()) {
				MAP[i][idx] = Integer.parseInt(st.nextToken());
				idx ++;
			}
		
		}
		while(true) {
			isPossible = false;
			for(int i= 0 ; i < N; i++) {
				for(int j = 0; j < N; j++) {
					if( visited[i][j] ) continue;
					move(i,j);
					
				}
			}
			//printMap();
			if(!isPossible) {
				System.out.println(CNT);
				return;
			}
			CNT +=1;
			visited = new boolean[101][101];
		}
	
	}
	public static void printMap() {
		System.out.println();
		for(int i= 0 ; i < N; i++) {
			for(int j = 0; j < N; j++) {
				System.out.print(MAP[i][j] + " ");
			}
			System.out.println();
		}
	}
	
	
	public static void move(int y, int x) {
		boolean flag = false;
		q.add(new Land(y,x));
		//visited[y][x] = true;
		//openList.add(new Land(y, x));
		while(!q.isEmpty()) {
			Land land = q.poll();
			for(int i = 0 ; i < 4; i++) {
				int yy = land.y + dy[i];
				int xx = land.x + dx[i];
				if( yy >= 0 && yy < N && xx >=0 && xx < N) {
					//이미 방문한적 있으면 
					if( visited[yy][xx] ) continue;
					int gap = Math.abs(MAP[land.y][land.x] - MAP[yy][xx]);
					if( L <= gap && gap <= R ) { 
						q.add(new Land(yy,xx));
						visited[yy][xx] = true;
						openList.add(new Land(yy,xx));
						isPossible = true;
						flag = true;
					}
					
				}
				
			}
		}
		//이동할 연합이 있으면 
		if( flag ) {
			int size = openList.size();
			if(size == 1) {
				return;
			}
			int sum = 0;
			for(int i =0 ; i < size; i++) {
				Land land = openList.get(i);
				sum += MAP[land.y][land.x];
			}
			for(int i =0 ; i < size; i++) {
				Land land = openList.get(i);
				MAP[land.y][land.x] = sum / size ;
			}
			openList.clear();
		}
		
	}
	
	
	

}