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

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

public class Main {
    public static int N, M, K, answer = Integer.MAX_VALUE;
    public static int[][] arr, calc;

    public static int[] order; // 연산 순서
    public static boolean[] visit;

    public static int[] dx = {1, 0, -1, 0}; // 하, 우, 상, 좌
    public static int[] dy = {0, 1, 0, -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());
        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());
            }
        }

        calc = new int[K][3];
        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            calc[i][0] = Integer.parseInt(st.nextToken()) - 1;
            calc[i][1] = Integer.parseInt(st.nextToken()) - 1;
            calc[i][2] = Integer.parseInt(st.nextToken());
        }

        order = new int[K];
        visit = new boolean[K];
        permutation(0);

        System.out.println(answer);
    }

    public static void rotate() {
        int[][] copy = new int[N][M]; // 임의 배열
        for (int i = 0; i < N; i++) {
            copy[i] = arr[i].clone();
        }

        for (int o : order) { // 연산 순서
            int r = calc[o][0];
            int c = calc[o][1];
            int s = calc[o][2];

            // 회전할 배열의 좌표 범위
            int minX = r - s, minY = c - s;
            int maxX = r + s, maxY = c + s;

            // 가장자리부터 안쪽까지 s번 회전하면 된다.
            for (int t = 0; t < s; t++) {
                int temp = copy[minX][minY];

                int curR = minX, curC = minY;
                int d = 0;

                while (true) { // 배열 회전
                    int nx = curR + dx[d];
                    int ny = curC + dy[d];

                    // 회전 범위를 벗어나면 방향 변환
                    if (nx < minX || nx > maxX || ny < minY || ny > maxY) {
                        d = ++d % 4;

                        nx = curR + dx[d];
                        ny = curC + dy[d];
                    }

                    // 최초 지점으로 복귀시 종료
                    if (nx == minX && ny == minY) {
                        break;
                    }

                    // 다음 번 칸의 값을 가져와 저장
                    copy[curR][curC] = copy[nx][ny];

                    // 다음 번 칸으로 이동
                    curR = nx;
                    curC = ny;
                }

                copy[minX][minY + 1] = temp;

                // 회전 범위 축소
                minX++; minY++;
                maxX--; maxY--;
            }
        }

        // 각 행에 있는 모든 수의 합 중 최솟값을 갱신
        for (int[] r : copy) {
            int sum = 0;

            for (int c : r) {
                sum += c;
            }

            answer = Math.min(answer, sum);
        }
    }

    // 연산 순서의 조합을 찾아 회전
    public static void permutation(int depth) {
        if (depth == K) {
            rotate();

            return;
        }

        for (int i = 0; i < K; i++) {
            if (!visit[i]) {
                visit[i] = true;

                order[depth] = i;
                permutation(depth + 1);

                visit[i] = false;
            }
        }
    }
}