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

입력

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

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

출력

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

---

solution.java

package 강수지;

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

public class P028_BJ17406_배열돌리기4 {
	static int N, M, K, min;
    static int arr[][]; // 원본 배열
    static int rotation[][]; // 회전 배열
	static int[] numbers; // 연산 정보를 위해
	static boolean[] isSelected;
	
	public static void main(String[] args) throws Exception {
		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()); // 연산 횟수
		
		arr = new int[N][M];
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		} // 배열 입력
		
		rotation = new int[K][3]; // rcs
		
		for (int i = 0; i < K; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 3; j++) {
				rotation[i][j] = Integer.parseInt(st.nextToken());
			}
		} // 회전 연산 정보
		
		numbers = new int[K];
		isSelected = new boolean[K];
		min = Integer.MAX_VALUE;
		
		Permutation(0); // 회전 연산을 수행한 순서에 따라 최종 배열이 다르다 = 순열 ..
		
		System.out.println(min);
		
	}

	static void Permutation(int cnt) { // 순열 컴온 ..
		if(cnt == K) {
			int[][] tmp = new int[N][M];
			
			for(int i = 0; i<N; i++) {
				for(int j = 0; j<M; j++) {
					tmp[i][j] = arr[i][j];
				}
			} // 원본 복사
			
			for(int i = 0; i<K; i++) {
				int x1 = rotation[numbers[i]][0] - rotation[numbers[i]][2] - 1; //r-s
				int y1 = rotation[numbers[i]][1] - rotation[numbers[i]][2] - 1; //c-s
				int x2 = rotation[numbers[i]][0] + rotation[numbers[i]][2] - 1; //r+s
				int y2 = rotation[numbers[i]][1] + rotation[numbers[i]][2] - 1; //c+s

				Rotate(x1, y1, x2, y2, tmp);
			} // 연산 정보 횟수만큼 돌면서 확인
			
			Min(tmp);
			
			return;
		}
		
		for (int i = 0; i < K; i++) {
			if(isSelected[i]) continue;
			numbers[cnt] = i;
			isSelected[i] = true;
			Permutation(cnt+1);
			isSelected[i] = false;
		}
		
	}

	static void Rotate(int x1, int y1, int x2, int y2, int[][] tmp) { // 회전 .. 인덱스 주의
        if(x1 == x2 && y1 == y2) {
            return;
        }
        
        int[] ver = new int[3];
        ver[0] = tmp[x1][y2];
        ver[1] = tmp[x2][y2];
        ver[2] = tmp[x2][y1];
        
        for(int i = y2; i > y1; i--) {
            tmp[x1][i] = tmp[x1][i - 1];
        }

        for(int i = x2; i > x1; i--) {
            if(i == x1 + 1) tmp[i][y2] = ver[0];
            else tmp[i][y2] = tmp[i - 1][y2];
        }

        for(int i = y1; i < y2; i++) {
            if(i == y2 - 1) tmp[x2][i] = ver[1];
            else tmp[x2][i] = tmp[x2][i + 1];
        }

        for(int i = x1; i < x2; i++) {
            if(i == x2 - 1) tmp[i][y1] = ver[2];
            else tmp[i][y1] = tmp[i + 1][y1];
        }    
        
        Rotate(x1 + 1, y1 + 1, x2 - 1, y2 - 1, tmp);
    } // rotate end
	
	static void Min(int[][] tmp) {
		for(int i = 0; i < N; i++) {
			int sum = 0;
			for(int j = 0; j < M; j++) {
				sum += tmp[i][j];
			}
			
			min = Math.min(min, sum);
		}
	} // 각 행의 최소값을 답으로 내기 위해 ..
}

---

출처

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

17406번: 배열 돌리기 4