[백준] 배열돌리기4 17406

문제

크기가 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의 크기가 5×6이고, 회전 연산이 (3, 4, 2), (4, 2, 1)인 경우의 예시이다.

배열 A에 (3, 4, 2), (4, 2, 1) 순서로 연산을 수행하면 배열 A의 값은 12, (4, 2, 1), (3, 4, 2) 순서로 연산을 수행하면 15 이다.

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

입력

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

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

출력

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

제한

• 3 ≤ N, M ≤ 50
• 1 ≤ K ≤ 6
• 1 ≤ A[i][j] ≤ 100
• 1 ≤ s
• 1 ≤ r-s < r < r+s ≤ N
• 1 ≤ c-s < c < c+s ≤ M

예제 입력 1

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

예제 출력 1

12

 

순회 연산의 순서가 정해져 있지 않고, 순회 연산을 마친 후 행의 합을 구해야 하기 때문에,

완전탐색을 통해 순회 연산의 순서가 될 수 있는 경우를 모두 뽑는다.

기존의 배열은 계속 사용해야 하기 때문에 복사하여 사용한다.

 

뽑은 순회 연산에서 사용해야 할 인덱스를 구하기 위해 X 시작 인덱스, X 끝 인덱스, Y 시작 인덱스 , Y 끝 인덱스를 구한다.

 

해당 구한 인덱스의 배열 내에서 시계방향으로 돌리기 위해 시작점에선 x한칸 아래에 있는걸 가져오고 이후 계속 돌면서 자신의 숫자를 temp에 저장하면서 다음으로 넘겨준다.

한바퀴를 다 돌았다면, X인덱스들을 1씩 더하고, Y인덱스들을 1씩 빼서 배열의 크기를 줄인 후 시작 인덱스와 끝 인덱스가 같아질때까지 반복한다.

 

풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class 배열돌리기_17406 {
    static int[] answer;
    static boolean[] visit;
    static List<Integer> seeList = new ArrayList<>();

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out);
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        int[][] arr = new int[n][m];
        List<Integer>[] rotaNum = new List[k];
        answer = new int[k];
        visit = new boolean[k];

        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());
            }
        }

        for(int i = 0; i<k; i++){
            st = new StringTokenizer(br.readLine());
            List<Integer> list = new ArrayList<>();
            for(int j = 0; j<3; j++){
                list.add(Integer.parseInt(st.nextToken()));
            }
            rotaNum[i] = list;
        }

        rotation(0,k, rotaNum, arr);

        int min = Integer.MAX_VALUE;
        for(int i = 0; i< seeList.size(); i++){
            min = Math.min(min,seeList.get(i));
        }

        pw.println(min);

        br.close();
        pw.close();
    }

    public static void rotation(int cnt, int k,List<Integer>[] rotaNum, int[][] arr) {
        if(cnt >= k) {

            int[][] tempArr = new int[arr.length][arr[0].length];

            for(int i = 0; i<arr.length; i++) {
                System.arraycopy(arr[i],0,tempArr[i],0,arr[0].length);
            }

            int startIdxX = 0;
            int startIdxY = 0;
            int endIdxX = 0;
            int endIdxY = 0;
            for(int i = 0; i<answer.length; i++){
                startIdxX = rotaNum[answer[i]].get(0) - rotaNum[answer[i]].get(2)-1;
                startIdxY = rotaNum[answer[i]].get(1) - rotaNum[answer[i]].get(2)-1;
                endIdxX = rotaNum[answer[i]].get(0) + rotaNum[answer[i]].get(2)-1;
                endIdxY = rotaNum[answer[i]].get(1) + rotaNum[answer[i]].get(2)-1;

                turn(startIdxX,startIdxY,endIdxX,endIdxY,tempArr);
            }

            int min = Integer.MAX_VALUE;
            for(int j = 0; j< tempArr.length; j++){
                int sum = 0;
                for(int l = 0; l<tempArr[0].length; l++) {
                    sum += tempArr[j][l];
                }
                min = Math.min(min,sum);
            }

            seeList.add(min);
            return;
        }

        for(int i = 0; i<k; i++){
            if(!visit[i]){
                answer[cnt] = i;
                visit[i] = true;
                rotation(cnt+1,k,rotaNum,arr);
                visit[i] = false;
            }
        }

    }

    public static void turn(int startIdxX,int startIdxY,int endIdxX,int endIdxY,int[][] tempArr) {

        if(startIdxX >= endIdxX || startIdxY >= endIdxY) {
            return;
        }

        int temp = 0;
        int temp2 = 0;
        int turn = 0;
        int i = startIdxX;
        int j = startIdxY;

        temp = tempArr[i][j];
        tempArr[i][j] = tempArr[i+1][j];
        j++;

        while(true){

            if(i==startIdxX && j ==startIdxY) {
                turn++;
                if(turn == 1) {
                    break;
                }
            }
            if(j < endIdxY && i == startIdxX) {
                temp2 = temp;
                temp = tempArr[i][j];
                tempArr[i][j] = temp2;
                j++;
                continue;
            }

            if(i < endIdxX && j == endIdxY) {
                temp2 = temp;
                temp = tempArr[i][j];
                tempArr[i][j] = temp2;
                i++;
                continue;
            }

            if(j> startIdxY && i == endIdxX) {
                temp2 = temp;
                temp = tempArr[i][j];
                tempArr[i][j] = temp2;
                j--;
                continue;
            }

            if(i> startIdxX && j == startIdxY) {
                temp2 = temp;
                temp = tempArr[i][j];
                tempArr[i][j] = temp2;
                i--;
                continue;
            }
        }

        turn(startIdxX+1,startIdxY+1,endIdxX-1,endIdxY-1,tempArr);

    }
}