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

순열 문제입니다.

 

회전 정보가 주어졌을 때, 각 행의 최소 합을 구하는 문제입니다.

문제 조건에 나와있듯이, 회전 순서에 따라 행의 최소 합이 달라집니다.

접근 순서는 다음과 같습니다.

1. 회전 정보를 저장한다.
2. 회전 정보를 바탕으로 정보의 순열을 구한다.
3. 순열 만큼 반복하여 회전하여 행의 최소 합을 구한다.

※ 주의할 점

직사각형 회전이 아닙니다.

제일 먼저 바깥쪽 테두리를 회전하고, 안쪽 테두리를 회전해야 합니다.

재귀를 통해 구현할 수 있습니다.

 

 

[구현 코드]

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    private static int n, m, k;
    private static List<List<Info>> orders;

    private static class Info {
        int a, b, c;

        public Info(int a, int b, int c) {
            this.a = a;
            this.b = b;
            this.c = c;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stz = new StringTokenizer(br.readLine(), " ");

        n = Integer.parseInt(stz.nextToken());
        m = Integer.parseInt(stz.nextToken());
        k = Integer.parseInt(stz.nextToken());

        int[][] map = new int[n][m];

        for (int i = 0; i < n; i++) {
            stz = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(stz.nextToken());
            }
        }

        // 회전 정보를 저장
        Info[] rotates = new Info[k];
        for (int i = 0; i < k; i++) {
            stz = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(stz.nextToken());
            int b = Integer.parseInt(stz.nextToken());
            int c = Integer.parseInt(stz.nextToken());

            rotates[i] = new Info(a, b, c);
        }

        // 저장된 회전 정보의 순열을 만듦
        orders = new ArrayList<>();
        permu(rotates, 0);


        int answer = Integer.MAX_VALUE;
        for (List<Info> order : orders) {
            int[][] cloneMap = new int[n][m];
            for(int i=0; i<n; i++) System.arraycopy(map[i], 0, cloneMap[i], 0, map[i].length);

            for (Info node : order) {
                rotateMap(cloneMap, node);
            }

            // 각 행의 최솟값을 구해서 최소 갱심함
            answer = Math.min(answer, minValue(cloneMap));
        }

        bw.write(String.valueOf(answer));

        bw.flush();
        bw.close();
        br.close();
    }

    private static int minValue(int[][] cloneMap){
        int min = Integer.MAX_VALUE;
        for(int i=0; i<n; i++){
            int rowTotal = 0;
            for(int j=0; j<m; j++){
                rowTotal += cloneMap[i][j];
            }
            min = Math.min(min, rowTotal);
        }
        return min;
    }

    private static void rotateMap(int[][] cloneMap, Info node) {
        int r1 = node.a - node.c - 1;
        int c1 = node.b - node.c - 1;
        int r2 = node.a + node.c - 1;
        int c2 = node.b + node.c - 1;

        rotateMapInRange(cloneMap, r1, c1, r2, c2);
    }

    private static void rotateMapInRange(int[][] cloneMap, int r1, int c1, int r2, int c2) {
        if(r1 == r2 && c1 == c2) return;

        int t1, t2, t3, t4;

        // 1
        t1 = cloneMap[r1][c2];
        for (int i = c2; i > c1; i--) {
            cloneMap[r1][i] = cloneMap[r1][i - 1];
        }

        // 2
        t2 = cloneMap[r2][c2];
        for (int i = r2; i > r1; i--) {
            cloneMap[i][c2] = cloneMap[i - 1][c2];
        }

        // 3
        t3 = cloneMap[r2][c1];
        for (int i = c1; i < c2; i++) {
            cloneMap[r2][i] = cloneMap[r2][i + 1];
        }

        // 4
        t4 = cloneMap[r1][c1];
        for (int i = r1; i < r2; i++) {
            cloneMap[i][c1] = cloneMap[i + 1][c1];
        }

        cloneMap[r1 + 1][c2] = t1;
        cloneMap[r2][c2 - 1] = t2;
        cloneMap[r2 - 1][c1] = t3;
        cloneMap[r1][c1 + 1] = t4;

        // 재귀를 통해 안쪽 테두리 회전
        rotateMapInRange(cloneMap, r1+1, c1+1, r2-1, c2-1);
    }

    // 순열
    private static void permu(Info[] rotates, int depth) {
        if (depth == k) {
            List<Info> order = new ArrayList<>();
            for (Info rotate : rotates) {
                order.add(new Info(rotate.a, rotate.b, rotate.c));
            }
            orders.add(order);
            return;
        }

        for (int i = depth; i < k; i++) {
            swap(rotates, depth, i);
            permu(rotates, depth + 1);
            swap(rotates, depth, i);
        }
    }

    private static void swap(Info[] rotates, int depth, int i) {
        Info tmp = rotates[depth];
        rotates[depth] = rotates[i];
        rotates[i] = tmp;
    }
}