[백준 JAVA] 17406 배열 돌리기 4

문제

---

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

17406번: 배열 돌리기 4

 

 

풀이방법

---

회전 순서에 따라 최종 배열이 다르기 때문에 순열코들르 사용하여, 회전연산의 순서를 정해주어야 한다.

 

순서를 정하면, 움직일 정도인 sx, sy, ex,ey를 구해준 후 spin함수를 사용해서 배열을 돌려준다.

시계 방향으로 한 칸씩 돌리기 위해서 아래와 같이 방향을 4가지로 나눠서 배열을 돌려주었다.

spin 코드는 아래와 같다.

	//배열 돌리기
	static void spin() {
			for(int j=0; j<spintime; j++) {
				//맨 왼쪽
				for(int k=j+1; k<=size-j-1; k++) {
					tempmove[k-1][j]=move[k+sx][j+sy];
				}
				//아래쪽
				for(int k=j+1; k<=size-j-1; k++) {
					tempmove[size-1-j][k-1]=move[size-1-j+sx][k+sy];
				}
				
				//맨 오른쪽
				for(int k=size-1-j; k>j; k--) {
					tempmove[k][size-1-j]=move[k-1+sx][size-1-j+sy];
				}
				
				//맨 위쪽
				for(int k=size-1-j; k>j; k--) {
					tempmove[j][k]=move[j+sx][k-1+sy];
				}
				
			}
			tempmove[size/2][size/2]=move[sx+size/2][sy+size/2];
			
			for(int k=0; k<size; k++) {
				for(int z=0; z<size; z++) {
					move[k+sx][z+sy]=tempmove[k][z];
				}
			}
	}

 

마지막으로 getmin함수를 사용해서 배열의 값의 최솟값을 출력한다.

최종 코드는 아래와 같다.

코드

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main{

	static int N,M,K,sx,sy,ex,ey;
	static int move[][];
	static int move2[][];
	static int spin[][];
	static int spintime;
	static int tempmove[][];
	static int size;
	static int[] num;
	static boolean select[];
	static int answer=Integer.MAX_VALUE;
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		
		move=new int[N][M];
		move2=new int[N][M];
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<M; j++) {
				move[i][j]=Integer.parseInt(st.nextToken());
			}
		}
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				move2[i][j]=move[i][j];
			}
		}
		
		
		spin= new int[K][3];
		
		for(int i=0; i<K; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<3; j++) {
				spin[i][j]=Integer.parseInt(st.nextToken());
			}
		}
		
		//k개중에 순서 정하기
		num=new int[K];
		select = new boolean[K];
		perm(0);
		System.out.println(answer);

	}
	
	
	static void perm(int cnt) {
		if(cnt==K) {
			for(int i:num) {
				sx=spin[i][0]-spin[i][2]-1;
				sy=spin[i][1]-spin[i][2]-1;
				ex=spin[i][0]+spin[i][2]-1;
				ey=spin[i][1]+spin[i][2]-1;
				size=spin[i][2]*2+1;
				tempmove = new int[size][size];
				spintime=(spin[i][2]*2+1)/2;
				spin();
			}
//			for(int i=0; i<N; i++) {
//				for(int j=0; j<M; j++) {
//					System.out.print(move[i][j]);
//				}
//				System.out.println();
//			}
			answer=Math.min(answer, getMin());
			//move초기화
			for(int i=0; i<N; i++) {
				for(int j=0; j<M; j++) {
					move[i][j]=move2[i][j];
				}
			}
			return;
			} 
		for(int i=0; i<K; i++) {
			if(select[i]==true) continue;
			num[cnt]=i;
			select[i]=true;
			perm(cnt+1);
			select[i]=false;
		 
		}
	}
	
	
	//배열 돌리기
	static void spin() {
			for(int j=0; j<spintime; j++) {
				//맨 왼쪽
				for(int k=j+1; k<=size-j-1; k++) {
					tempmove[k-1][j]=move[k+sx][j+sy];
				}
				//아래쪽
				for(int k=j+1; k<=size-j-1; k++) {
					tempmove[size-1-j][k-1]=move[size-1-j+sx][k+sy];
				}
				
				//맨 오른쪽
				for(int k=size-1-j; k>j; k--) {
					tempmove[k][size-1-j]=move[k-1+sx][size-1-j+sy];
				}
				
				//맨 위쪽
				for(int k=size-1-j; k>j; k--) {
					tempmove[j][k]=move[j+sx][k-1+sy];
				}
				
			}
			tempmove[size/2][size/2]=move[sx+size/2][sy+size/2];
			
			for(int k=0; k<size; k++) {
				for(int z=0; z<size; z++) {
					move[k+sx][z+sy]=tempmove[k][z];
				}
			}
	}

	
	//최솟값 찾기
	static int getMin() {
		int add =0;
		int min=Integer.MAX_VALUE;
		
		for(int i=0; i<N; i++) {
			add=0;
			for(int j=0; j<M; j++) {
				add=add+move[i][j];
			}
			min=Math.min(add, min);
		}
		return min;
	}

}