[BOJ] 백준 23291 어항 정리

배열 회전 + 옮기기 어렵당...ㅎㅇㅌ

 

[문제]

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

 

[소스 코드]

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

public class Main {
	static int n,k;
	static int[][] aquarium;
	static int[] dr = {-1,1,0,0};
	static int[] dc = {0,0,-1,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());
    	aquarium = new int[n][n];
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<n;i++) {
    		aquarium[n-1][i] = Integer.parseInt(st.nextToken());
    	}
    	int result = 0;
    	while(!isFinish()) {
    		addFish();
    		firstFold();
    		balance();
   
    		make1D();
    		secondFold();
    		balance();
    		make1D();
    		result++;
    	}
    	System.out.println(result);
    }
    private static boolean isFinish() {
    	int min = Integer.MAX_VALUE;
    	int max = Integer.MIN_VALUE;
    	for(int i=0;i<n;i++) {
    		min = Math.min(min, aquarium[n-1][i]);
    		max = Math.max(max,aquarium[n-1][i]);
    	}
    	return max - min <= k;
    }
    private static void addFish() {
    	int min = Integer.MAX_VALUE;
    	for(int i=0;i<n;i++) {
    		min = Math.min(min, aquarium[n-1][i]);
    	}
    	for(int i=0;i<n;i++) {
    		if(aquarium[n-1][i]==min) {
    			aquarium[n-1][i]++;
    		}
    	}
    }
    private static void firstFold() {
    	int startX = 0;
    	int w = 1;
    	int h = 1;
    	while(startX + w + h <= n) {
    		for(int r=n-1;r>=n-h;r--) {
    			for(int c=startX;c<startX+w;c++) {
    				int newR = (n-1-w) + (c-startX);
    				int newC = (startX+w) + (n-1-r);
    				
    				aquarium[newR][newC] = aquarium[r][c];
    				aquarium[r][c] = 0;
    			}
    		}   
    		startX += w;
    		if(w==h) h++;
    		else w++;
    	}
    }
    private static void balance() {
    	int[][] plus = new int[n][n];
    	for(int i=0;i<n;i++) {
    		plus[i] = aquarium[i].clone();
    	}
    	for(int i=0;i<n;i++) {
    		for(int j=0;j<n;j++) {
    			if(aquarium[i][j]==0) continue;
    			for(int d=0;d<4;d++) {
    				int nr = i + dr[d];
    				int nc = j + dc[d];
    				if(!isRange(nr,nc) || aquarium[nr][nc]==0) continue;
    				if(aquarium[i][j]>aquarium[nr][nc]) {
    					int diff = (aquarium[i][j]-aquarium[nr][nc])/5;
    					plus[i][j] -= diff;
    					plus[nr][nc] += diff;
    				}
    			}
    		}
    	}
    	aquarium = plus;
    }
    private static void make1D() {
    	int[] flattern = new int[n];
    	int idx = 0;
    	for(int i=0;i<n;i++) {
    		for(int j=n-1;j>=0;j--) {
    			if(aquarium[j][i]==0) continue;
    			flattern[idx++] = aquarium[j][i];
    			aquarium[j][i] = 0;
    		}
    	}
    	for(int i=0;i<n;i++) {
    		aquarium[n-1][i] = flattern[i];
    	}
    }
    private static void secondFold() {
    	int quarterN = n/4;
    	int c = 0;
    	int[] sCol = {0,n-1,n-quarterN,n-1};
    	int[] cDir = {0,-1,1,-1};
    	for(int i=1;i<=3;i++) {
    		int col = sCol[i];
    		for(int j=0;j<quarterN;j++) {
    			aquarium[n-1-i][col] = aquarium[n-1][c];
    			aquarium[n-1][c] = 0;
    			col += cDir[i];
    			c++;
    		}
    	}
    }
    private static boolean isRange(int r,int c) {
    	return r>=0 && c>=0 && r<n && c<n;
    }
}