[Java] 백준 / 배열 돌리기 4 / 17406번

[Java] 백준 / 배열 돌리기 4 / 17406번

문제

배열 돌리기4 문제 링크

크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 값은 4이다.

1 2 3
2 1 1
4 5 6

배열은 회전 연산을 수행할 수 있다. 회전 연산은 세 정수 (r, c, s)로 이루어져 있고, 가장 왼쪽 윗 칸이 (r-s, c-s), 가장 오른쪽 아랫 칸이 (r+s, c+s)인 정사각형을 시계 방향으로 한 칸씩 돌린다는 의미이다. 배열의 칸 (r, c)는 r행 c열을 의미한다.

예를 들어, 배열 A의 크기가 6×6이고, 회전 연산이 (3, 4, 2)인 경우에는 아래 그림과 같이 회전하게 된다.

A[1][1]   A[1][2] → A[1][3] → A[1][4] → A[1][5] → A[1][6]
             ↑                                       ↓
A[2][1]   A[2][2]   A[2][3] → A[2][4] → A[2][5]   A[2][6]
             ↑         ↑                   ↓         ↓
A[3][1]   A[3][2]   A[3][3]   A[3][4]   A[3][5]   A[3][6]
             ↑         ↑                   ↓         ↓
A[4][1]   A[4][2]   A[4][3] ← A[4][4] ← A[4][5]   A[4][6]
             ↑                                       ↓
A[5][1]   A[5][2] ← A[5][3] ← A[5][4] ← A[5][5] ← A[5][6]

A[6][1]   A[6][2]   A[6][3]   A[6][4]   A[6][5]   A[6][6]

회전 연산이 두 개 이상이면, 연산을 수행한 순서에 따라 최종 배열이 다르다.

배열 A에 (3, 4, 2), (4, 2, 1) 순서로 연산을 수행하면 배열 A의 값은 12, (4, 2, 1), (3, 4, 2) 순서로 연산을 수행하면 15 이다.

배열 A와 사용 가능한 회전 연산이 주어졌을 때, 배열 A의 값의 최솟값을 구해보자. 회전 연산은 모두 한 번씩 사용해야 하며, 순서는 임의로 정해도 된다.

입력

첫째 줄에 배열 A의 크기 N, M, 회전 연산의 개수 K가 주어진다.

둘째 줄부터 N개의 줄에 배열 A에 들어있는 수 A[i][j]가 주어지고, 다음 K개의 줄에 회전 연산의 정보 r, c, s가 주어진다.

5 6 2
1 2 3 2 5 6
3 8 7 2 1 3
8 2 3 1 4 5
3 4 5 1 1 1
9 3 2 1 4 3
3 4 2
4 2 1

출력

배열 A의 값의 최솟값을 출력한다.

12

접근 방식

1. 순열을 구현하고 회전 수만큼 순열 리스트를 만든다
2. 행렬의 부분 정사각형을 회전하는 함수를 구현한다
3. 순열 리스트에서 하나씩 가져와 해당 순서로 회전 시킨다
4. 회전 시킨 배열의 행 합 중 가장 낮은 값을 저장한다

코드

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

public class Main_17406_정현명 {

	static int matrix[][]; // 원 배열 저장
	static int temp[][]; // 임시 저장 
	static int n,m,k;
	static int[][] deltas = {{1,0},{0,1},{-1,0},{0,-1}};
	static List<int[]> list = new ArrayList<>(); // 회전 순서 순열 리스트
	static int rotateArr[][]; // 회전 정보
	static int minRowSum = Integer.MAX_VALUE; // 가장 낮은 행 합값
	
	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());
		m = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		
	
		matrix = new int[n+1][m+1];
		
		for(int i=1;i<=n;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=1;j<=m;j++) {
				matrix[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		rotateArr = new int[k][3];
		
		
		for(int i=0;i<k;i++) {
			st = new StringTokenizer(br.readLine());
			rotateArr[i][0] = Integer.parseInt(st.nextToken());
			rotateArr[i][1] = Integer.parseInt(st.nextToken());
			rotateArr[i][2] = Integer.parseInt(st.nextToken());
		}
		
		// =============== 회전 순서 리스트 만들기 ==============
		int numbers[] = new int[k];
		boolean selected[] = new boolean[k];
		permutation(0, numbers, selected ); // 순열을 통해 kPk 크기의 순서 배열을 list에 저장한다
		
		// =============== 회전 순서 리스트에서 하나씩 빼서 순서에 맞게 회전 한 후 회전 된 행렬의 값(행 합중 가장 낮은 값)을 구한다 ================
		for(int i=0;i<list.size();i++) {
			
			// 회전시킬 배열 생성
			temp = new int[n+1][m+1];
			
			// 깊은 복사 
			for(int r=1;r<=n;r++) {
				for(int c=1;c<=m;c++) {
					temp[r][c] = matrix[r][c];
				}
			}
			
			// r, c, s를 가진 int 배열 가져오기
			int rotateInfo[] = list.get(i);
			
			// 순서에 맞게 회전
			for(int j : rotateInfo) {
				rotate(rotateArr[j][0],rotateArr[j][1],rotateArr[j][2]);
			}
			
			// 회전한 배열을 탐색하여 최소 행합을 구함
			searchMinRowSum();
		}
		
		// ================ 여러 배열의 행 합중 가장 낮은 값 출력 ==============
		
		System.out.println(minRowSum);
	}
	
	
	public static void rotate(int r, int c, int s) {
		
		int leftUpR = r-s; 
		int leftUpC = c-s; 
		int rightDownR = r+s; 
		int rightDownC = c+s;
		
		int size = rightDownR - leftUpR + 1;
		
		// 부분 네모 
		for(int i=0;i<size/2;i++) {
			int firstR = leftUpR + i; 
			int firstC = leftUpC + i; 
			
			int firstValue = temp[firstR][firstC];
			
			int R = firstR;
			int C = firstC;
			
			for(int j=0;j<4;j++) {
				while(true) {
					int nextR = R + deltas[j][0];
					int nextC = C + deltas[j][1];
					
					if(nextR < leftUpR + i || nextR > rightDownR - i || nextC < leftUpC + i || nextC > rightDownC - i) break; 
					temp[R][C] = temp[nextR][nextC];
					R = nextR;
					C = nextC;
					
				}
			}
			
			temp[firstR][firstC+1] = firstValue;
		}
	}
	
	public static void searchMinRowSum() {
		for(int i=1;i<=n;i++) {
			int sum =0;
			for(int j=1;j<=m;j++) {
				sum+=temp[i][j];
			}
			
			minRowSum = Math.min(minRowSum, sum);
		}
		
	}
	
	
	// 순열
	public static void permutation(int cnt, int[] numbers, boolean[] selected) {
		if(cnt == k) {
			list.add(numbers.clone());
		}
		
		for(int i=0;i<k;i++) {
			if(selected[i] == false) {
				numbers[cnt] = i;
				selected[i] = true;
				permutation(cnt+1,numbers,selected);
				selected[i] = false;
			};
		}
	}

}