[BOJ] 백준 17406 배열 돌리기 4

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

 Input 

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

 

 Output 

12

회전 연산]

6 x 6 배열과 (r, c, s) = (3, 4, 2) 일 때,

좌측 상단: (r-s, c-s) / 우측 하단: (r+s, c+s)

『배열 A의 값』은 각 행에 있는 모든 수의 합 중 최솟값을 의미.

주어진 회전을 순서로 임의로 배정했을 때, 『배열 A의 값』 중 최소값을 구하는 문제입니다. 

 

구현 순서

① 모든 회전 가능한 회전 경우의 수 구현 ← 순열 

② 회전 순서가 정해지면 배열 내부에서 특정 영역(정사각형)에 대한 회전(재배치)

     회전(재배치)을 시켜서 배열 A의 최솟값을 구합니다.

  

기준점을 좌측 상단 『1』을 기점으로 {테두리 길이 - 1} 만큼 순회합니다.

따라서, List = {2, 3, 4, 9, 14, 19, 18, 17, 16, 11, 6, 1} 담습니다.

맨 마지막 원소를 제일 앞에 둬서 List = {1, 2, 3, 4, 9, 14, 19, 18, 17, 16, 11, 6}

다시 배열을 순회하여 원소를 재할당하여 회전한 것처럼 구현합니다.

마찬가지로, 안쪽 테두리도 기준점을 『7』로 해서 동일한 작업을 반복합니다.

(이때, 테두리 길이는 {이전 길이 -2} 입니다.)

 

→ : 기준점『0』 / 테두리 길이 = 5

→ : 기준점『6』 / 테두리 길이 = 3

→ : 기준점 『12』 / 테두리 길이 = 1 

③ 주어진 회전 연산이 끝나면, 문제에서 배열 A의 값 중 최솟값을 구합니다.

---

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    
    static int[][] arr;
    static List<Rotate> list;
    static List<Rotate> rotateOrder;
    static boolean[] visited;
    static int N, M, K;
    static int answer = Integer.MAX_VALUE;
    
    static class Rotate{
        int ID;
        int r, c, s;
        
        public Rotate(int r, int c, int s, int ID) {
            this.r = r;
            this.c = c;
            this.s = s;
            this.ID = ID;
        }

        @Override
        public String toString() {
            return "[" + ID + "] ";
        }
    }
    
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N = Integer.parseInt(sc.next());
        M = Integer.parseInt(sc.next());        
        K = Integer.parseInt(sc.next());
        arr = new int[N+1][M+1];
        
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=M; j++) {
                arr[i][j] = Integer.parseInt(sc.next());
            }
        }
        
        list = new ArrayList<>();
        for(int i=0; i<K; i++) {
            list.add(new Rotate(
                    Integer.parseInt(sc.next()), // r
                    Integer.parseInt(sc.next()), // c
                    Integer.parseInt(sc.next()), // s
                    i // ID
                ));
        }
        
        visited = new boolean[K];
        rotateOrder = new ArrayList<>();
        perm();
        
        System.out.println(answer);
    }

    private static void perm() {
        if(rotateOrder.size() == K) {
            rotate(deepCopy(arr), rotateOrder);
            return;
        }
        
        for(int i=0; i<K; i++) {
            // 방문하지 않은 곳이라면
            if(!visited[i]) {
                rotateOrder.add(list.get(i));
                visited[i] = true;
                
                perm();
                
                rotateOrder.remove(rotateOrder.size()-1);
                visited[i] = false;
            }
        }
    }

    private static int[][] deepCopy(int[][] src) {
        int[][] dest = new int[N+1][M+1];
        for(int i=1; i<=N; i++) {
            System.arraycopy(src[i], 0, dest[i], 0, src[i].length);
        }
        return dest;
    }

    private static void rotate(int[][] arr, List<Rotate> rotateOrder) {
        // 주어진 회전 순서만큼
        for(int r=0; r<rotateOrder.size(); r++) {
            // 왼쪽 상단의 기준점
            Rotate obj = rotateOrder.get(r);
            int x = obj.r - obj.s;
            int y = obj.c - obj.s;
            
            // 최초 바깥쪽 테두리의 길이
            int len = (obj.s * 2) + 1;
            
            // 우, 하, 좌, 상(감싸는 방향)
            int[] dx = {0, 1, 0, -1};
            int[] dy = {1, 0, -1, 0};
            
            List<Integer> temp = new ArrayList<>();
            while(true) {
                for(int i=0; i<4; i++) {
                    // 할당된 테두리만큼 원소를 리스트에 담는다.
                    for(int l=1; l<len; l++) {
                        x = x + dx[i];
                        y = y + dy[i];
                        temp.add(arr[x][y]);
                    }
                }
                // 한 번 회전환 순서로 배치
                temp.add(0, temp.remove(temp.size()-1));
                
                // 재배치된 숫자를 다시 해당 테두리에 할당
                for(int i=0; i<4; i++) {
                    // 할당된 테두리만큼 원소를 리스트에 담는다.
                    for(int l=1; l<len; l++) {
                        x = x + dx[i];
                        y = y + dy[i];
                        arr[x][y] = temp.remove(0);
                    }
                }
                
                // 테두리 반경 줄여나가기
                len = len - 2;
                // 기준점도 따라서 재설정
                x++; y++;
                // 회전할 필요가 없을 때까지
                // 짝수로 시작했으면 0 / 홀수로 시작했으면 1
                if (len == 0 || len == 1) break;
            }
        }
        // 각각의 회전 순서 중 최솟값
        answer = Math.min(answer, solve(arr));
    }


    // 주어진 회전 순서에서 배열의 최솟값
    private static int solve(int[][] arr) {
        int temp = Integer.MAX_VALUE;
        for(int i=1; i<=N; i++) {
            int sum = 0;
            for(int j=1; j<=M; j++) {
                sum += arr[i][j];
            }
            temp = Math.min(temp, sum);
        }
        return temp;
    }
}