[Java] 17406 배열 돌리기 4

17406 배열 돌리기 4

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

17406번: 배열 돌리기 4

 

구현 + DFS (순열)

돌리는 경우의 수를 DFS로 구현해서 완성되면 배열 돌려기

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.io.FileInputStream;

class Solution {

    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};

    static int N, M, R, r, c, s, x, y, res;
    static int[] permutation;
    static boolean[] visited;
    static int[][] arr, arr2, rotation;

    static void insert(int cnt, int direction) {
        for (int i=0; i<cnt; i++) {
            arr[y][x] = arr[y + dy[direction]][x + dx[direction]];
            x = x + dx[direction];
            y = y + dy[direction];
        }
    }

    static void rotate() {
        for (int i=0; i<s; i++) {
            x = c - s - 1 + i;
            y = r - s - 1 + i;

            int direction = 0;
            int width = (s-i) * 2;
            int temp = arr[y][x];

            insert(width, direction);
            insert(width, direction + 1);
            insert(width, direction + 2);
            insert(width, direction + 3);

            arr[r - s - 1 + i][c - s + i] = temp;
        }
    }

    static int getMin() {
        int min = Integer.MAX_VALUE, sum = 0;
        for (int i=0; i<N; i++) {
            sum = 0;
            for (int j=0; j<M; j++) {
                sum += arr[i][j];
            }
            min = Math.min(min, sum);
        }
        return min;
    }

    static void dfs(int idx) {
        if (idx == R) {
            for (int i=0; i<N; i++) {
                for (int j=0; j<M; j++) {
                    arr[i][j] = arr2[i][j];
                }
            }
            for (int i=0; i<R; i++) {
                r = rotation[permutation[i]][0];
                c = rotation[permutation[i]][1];
                s = rotation[permutation[i]][2];
                rotate();
            }
            res = Math.min(getMin(), res);
            return;
        }

        for (int i=0; i<R; i++) {
            if (!visited[i]) {
                visited[i] = true;
                permutation[idx] = i;
                dfs(idx+1);
                visited[i] = false;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // testCase = Integer.parseInt(br.readLine());

        StringTokenizer token = new StringTokenizer(br.readLine());
        N = Integer.parseInt(token.nextToken());
        M = Integer.parseInt(token.nextToken());
        R = Integer.parseInt(token.nextToken());

        arr = new int[N][M];
        arr2 = new int[N][M];

        for (int i=0; i<N; i++) {
            token = new StringTokenizer(br.readLine());
            for (int j=0; j<M; j++) {
                arr[i][j] = Integer.parseInt(token.nextToken());
                arr2[i][j] = arr[i][j];
            }
        }

        rotation = new int[R][3];
        for (int i=0; i<R; i++) {
            token = new StringTokenizer(br.readLine());
            r = Integer.parseInt(token.nextToken());
            c = Integer.parseInt(token.nextToken());
            s = Integer.parseInt(token.nextToken());
            rotation[i][0] = r; rotation[i][1] = c; rotation[i][2] = s;
        }

        permutation = new int[R];
        visited = new boolean[R];
        res = Integer.MAX_VALUE;

        dfs(0);

        /* print */
        System.out.println(res + "\n");

        int[][] arr = new int[2][3];
        int[][] arr2 = new int[3][2];
        arr = arr2;

    }
}