[백준 17406] 배열 돌리기4(Java)

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

17406번: 배열 돌리기 4

문제

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

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

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

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

다음은 배열 A의 크기가 5×6이고, 회전 연산이 (3, 4, 2), (4, 2, 1)인 경우의 예시이다.

배열 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가 주어진다.

출력

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

제한

• 3 ≤ N, M ≤ 50
• 1 ≤ K ≤ 6
• 1 ≤ A[i][j] ≤ 100
• 1 ≤ s
• 1 ≤ r-s < r < r+s ≤ N
• 1 ≤ c-s < c < c+s ≤ M

예제 입력 1

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

예제 출력 1

12

풀이 설명

1. 각 연산 r,c,s를 필드로 가지는 클래스를 선언하고, 입력받을 때마다 객체를 생성하여 cals 배열에 넣어준다.

2. 이 문제는 '순열'이 필요한 문제이다. cals배열의 객체 원소들을 순열을 사용하여 나열하고, 각 순열마다의 연산 순서로 수행한 배열의 최솟값을 구해가며 가장 최소인 값을 찾아야 한다.

3. 순열을 구하는 permutation 함수 내에서, 하나의 순열이 완성될 때마다 그 순열을 넘겨 rotation 함수를 호출한다.

4. rotation 함수 내에서는, 넘겨받은 순열대로 연산들을 처리하고, 결과 배열의 최솟값을 찾는다.

  4-1. 연산을 처리하는 로직은 배열 돌리기 1,3과 같이 인덱스만 잘 조립?해주면 된다.

        재배열될 시작점과 끝점은 순열의 객체들이 가지고 있는 필드들을 문제에 나온대로 조합하여 구한다.

  4-2. 최솟값을 구했으면, 전체의 최솟값과 한번 더 비교하여 더 작은 값을 전체의 최솟값으로 갱신한다.

5. 주의해야 할 점!!하나의 순열대로 연산을 한 후, 다음 순열이 완성되어 또 연산을 해야 할 경우, 이전에 재배치된 배열이 아닌, 기존에 입력받은 arr배열로 연산을 해야한다.

  5-1. 따라서, rotation을 호출하기 전에 arr배열과 똑같은 배열 copyArr을 하나 만들어 이걸로 연산을 수행한다.

Java 코드

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

class Data {
	public int r;
	public int c;
	public int s;
	
	public Data(int r, int c, int s){
		this.r = r;
		this.c = c;
		this.s = s;
	}

	@Override
	public String toString() {
		return "Data [r=" + r + ", c=" + c + ", s=" + s + "]";
	}
	
}

public class Main {
	
	static Data[] cals;
	static int[][] arr;
	static int h;
	static int w;
	static int k;
	static int[][] copyArr;
	
	static int startX;
	static int startY;
	static int endX;
	static int endY;
	static int count;
	static int minVal;
	
	public static void rotation(Data[] temp) {
		for(int i=0; i<k; i++) {
			Data cal = temp[i];
			startX = cal.r - cal.s - 1;
			startY = cal.c - cal.s - 1;
			endX = cal.r + cal.s - 1;
			endY = cal.c + cal.s - 1;
			count = Math.min(endX - startX, endY - startY) / 2; //돌아가는 라인의 수
			
			for(int c=0; c<count; c++) { //라인 전부 돌리기
				int val = copyArr[startX+c][startY+c]; //(c,c)
				
				for(int j=startX+c; j<endX-c; j++) //왼쪽
					copyArr[j][startY+c] = copyArr[j+1][startY+c];
				for(int j=startY+c; j<endY-c; j++) //아래쪽
					copyArr[endX-c][j] = copyArr[endX-c][j+1];
				for(int j=endX-c; j>startX+c; j--) //오른쪽
					copyArr[j][endY-c] = copyArr[j-1][endY-c];
				for(int j=endY-c; j>startY+c; j--) //위쪽
					copyArr[startX+c][j] = copyArr[startX+c][j-1];
				
				copyArr[startX+c][startY+c+1] = val;
			}
			
		}
		int min = Integer.MAX_VALUE;
		for(int i=0; i<h; i++) {
			int cnt = 0;
			for(int j=0; j<w; j++)
				cnt += copyArr[i][j];
			min = Math.min(cnt, min);
		}
		minVal = Math.min(min, minVal);
	}
	
	public static void permutation(int r, int current, Data[] temp, boolean[] visited) {
		if(current == r) {
			copyArr = new int[h][w];
			for(int i=0; i<h; i++)
				for(int j=0; j<w; j++)
					copyArr[i][j] = arr[i][j];
			rotation(temp);
			return;
		}
		for(int i=0; i<cals.length; i++) {
			if(!visited[i]) {
				visited[i] = true;
				temp[current] = cals[i];
				permutation(r, current+1, temp, visited);
				visited[i] = false;
			}
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		h = Integer.parseInt(st.nextToken());
		w = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		
		arr = new int[h][w];
		for(int i=0; i<h; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<w; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		cals = new Data[k];
		for(int i=0; i<k; i++) {
			st = new StringTokenizer(br.readLine());
			int r = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			int s = Integer.parseInt(st.nextToken());
			cals[i] = new Data(r,c,s);
		}

		boolean[] visited = new boolean[k];
		Data[] temp = new Data[k];
		minVal = Integer.MAX_VALUE;
		permutation(k, 0, temp, visited);
		
		System.out.println(minVal);
	}
}