[백준] 23291. 어항 정리

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

23291번: 어항 정리

---

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

// [백준] 23291. 어항정리
public class Main {

	static int N, K, min, max, answer = 1;
	static int arr[][];
//	static int[][] dir = {{0,1}, {1,0}, {-1,0}, {0,-1}};
	static int[][] dir = {{1,0}, {0,1}};

	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());
		K = Integer.parseInt(st.nextToken());

		arr = new int[N][N];
		
		st = new StringTokenizer(br.readLine());
		
		min = Integer.MAX_VALUE;
		
		for (int i = 0; i < N; i++) {
			int num = Integer.parseInt(st.nextToken());
			min = Math.min(num, min);
			arr[N-1][i] = num;
		}
		
		while(true) {
			
			// 1. 먼저, 물고기의 수가 가장 적은 어항에 물고리를 한 마리 넣는다.
			for(int i=0; i<N; i++) {
				if(arr[N-1][i] == min) arr[N-1][i] += 1; 
			}
			
			int xLen = 1;
			int yLen = 0;
			
			boolean flag = false;
			
			// 2. 어항정리 1 
			arrange1(1, 0, 1, false, arr);
			
//		print(arr);
			
			// 3. 물고기수 조절
			adjust(arr);
			
			// 4. 바닥에 일렬로 놓는다.
			inLine(arr);
			
//		print(arr);
			
			// 5. 가운데를 중심으로 왼쪽 N/2개 공중부양
			arrange2(arr);
			
//		print(arr);
			
			// 6. 여기에서 다시 물고기 조절 작업
			adjust(arr);
			
			// 7. 바닥에 일렬로 놓는 작업
			inLine(arr);
			
//			print(arr);
			
			max = Integer.MIN_VALUE;
			min = Integer.MAX_VALUE;
			
			// 8. 물고기가 가장 많이 들어있는 어항과 가장 적게 들어있는 어항의 차이
			for(int j=0; j<N; j++) {
				if(arr[N-1][j] > max) max = Math.max(max, arr[N-1][j]);
				if(arr[N-1][j] < min) min = Math.min(min, arr[N-1][j]);
			}
			
//			System.out.println("max : " + max + " / min : " + min);
			
			if(max - min <= K) break;
			else answer++;
			
		}
			
		System.out.println(answer);
		
		
		
	}
	
	// flag가 true면 xLen temp 만큼 증가 
	// flag가 false면 yLen temp 만큼 증가
	public static void arrange1(int xLen, int yLen, int temp, boolean flag, int[][] arr) {
//		print();
		
		int Y = 0;
		
		while(true) {
			
			if (flag) xLen += temp;
			else yLen += temp;
			
//			System.out.println("xLen : " + xLen + " / yLen : " + yLen + " / Y : " + Y);
			
			if(xLen > (N-1)-(Y+yLen-1)) break;
			
			
			for (int j = 0; j < yLen; j++) {
				for (int i = 0; i < xLen; i++) {
					arr[N - 1 - (yLen - j)][Y + yLen + i] = arr[N - 1 - i][Y + j];
					arr[N - 1 - i][Y + j] = 0;
				}
			}
			
			flag = !flag;
			Y += yLen;
			
//			print();
			
//			if(xLen == 3) break;
		}
	}
	
	public static void arrange2(int[][] arr) {
		
		// 1. 가운데를 중심으로 N/2개를 공중부양 시켜 전체를 시계방향으로 180도 회전.
		int xLen = 1;
		int yLen = N/2;
		
		for(int j=0; j<yLen; j++) {
			arr[N-2][N-1-j] = arr[N-1][j];
			arr[N-1][j] = 0;
		}
		
		// 2. 두번반복
		xLen = 2;
		yLen = N/4;
		
		int Y = N/2;
		
		for(int i=0; i<xLen; i++) {
			for(int j=0; j<yLen; j++) {
				arr[N-3-i][N-1-j] = arr[N-2+i][Y+j];
				arr[N-2+i][Y+j] = 0;
			}
		}
	}
	
	public static void adjust(int[][] arr) {
		
		int[][] temp_arr = new int[N][N];
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				if(arr[i][j] != 0) {
					for(int k=0; k<2; k++) {
						int nx = i+dir[k][0];
						int ny = j+dir[k][1];
						
						if(isInside(nx, ny) && arr[nx][ny] != 0) {
							// 인접한 두 어항에서 대해서, 물고기 수의 차이를 구한다.
							int d = Math.abs(arr[i][j] - arr[nx][ny]) / 5;
							
							// d가 0보다 크면 물고기의 수가 많은 곳에서 적은 곳에 있는 곳으로 보낸다.
							if(d > 0) {
								if(arr[i][j] > arr[nx][ny]) {
									temp_arr[nx][ny] += d;
									temp_arr[i][j] -= d;
								}
								else {
									temp_arr[i][j] += d;	
									temp_arr[nx][ny] -= d;
								}
							}
						}
					}
				}
			}
		}
		
//		System.out.println("temp_arr 출력");
//		print(temp_arr);
		
		// 물고기 더하고 빼기
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				arr[i][j] += temp_arr[i][j];
			}
		}
		
//		print(arr);
	}
	
	public static void inLine(int[][] arr) {
		ArrayList<Integer> list = new ArrayList();
		
		for(int j=0; j<N; j++) {
			for(int i=N-1; i>=0; i--) {
				if(arr[i][j] == 0) break;
				else {
					list.add(arr[i][j]);
					arr[i][j] = 0;
				}
			}
		}
		
		for(int j=0; j<N; j++) {
			arr[N-1][j] = list.get(j);
		}
		
	}
	
	public static boolean isInside(int x, int y) {
		return x>=0 && y>=0 && x<N && y<N;
	}
	
	// a배열에 b배열을 복사한다.
	public static void copy(int[][] a, int[][] b) {
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				arr[i][j] = b[i][j];
			}
		}
	}
	
	public static void print() {
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				System.out.printf("%4d",arr[i][j]);
			}
			System.out.println();
		}
		System.out.println();
	}
	
	public static void print(int[][] a) {
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				System.out.printf("%4d",a[i][j]);
			}
			System.out.println();
		}
		System.out.println();
	}
}