[BOJ] 백준 17406 : 배열 돌리기 4 (java)

🧪 17406 배열 돌리기 4

---

난이도 : 🌟 골드 4
유형 : 구현

https://www.acmicpc.net/problem/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의 값의 최솟값을 출력한다.

 

🚧  주의할 점

---

1. 내부에 있는 배열도 회전해야 하기 때문에 s 값을 반복문을 통해 바꿔줘야 한다.

🧐 핵심 로직 

---

1) 회전 연산의 순서를 임의로 변경해야 하기 때문에 회전 연산 값들을 저장하고 있는 배열을 만들어준다.

 

2) permutation 함수를 만들어 임의의 순서로 회전연산이 실행될 수 있도록 한다.

    2 - a) 이때, 회전연산의 순서가 다 정해진다면 배열을 회전시키고 다른 순서로 다시 회전할 수 있도록 return 해준다.

 

3) 회전의 경우 외부와 내부가 모두 회전할 수 있도록 반복문을 사용하고, 사라지는 값들을 저장해두면서 한칸씩 회전시켜

빈자리에 저장해둔 사라지는 값을 대입해준다.

 

4) 결과값을 구하기 위해 각 행의 합을 구하고 가장 작은 값이 res에 저장될 수 있도록 한다.

 

5) res 값을 출력해준다.

 

💻 최종 코드 (364 ms)

---

import java.io.*;
import java.util.*;

public class Main {

    static int n, m, k;
    static int res = Integer.MAX_VALUE;
    static int[] arr;
    static boolean[] visited;
    static int[][] arrayMap;
    static int[][] rotation;
    public static void main(String[] args) throws IOException {

        // BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedReader br = new BufferedReader(new FileReader("input.txt"));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

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

        rotation = new int[k][3];
        for (int i = 0; i < k; i++) {
            st = new StringTokenizer(br.readLine());

            rotation[i][0] = Integer.parseInt(st.nextToken()) - 1;
            rotation[i][1] = Integer.parseInt(st.nextToken()) - 1;
            rotation[i][2] = Integer.parseInt(st.nextToken());
        }

        arr = new int[k];
        visited = new boolean[k];
        permutation(0);

        System.out.println(res);

        br.close();
    }

    private static void permutation(int idx) {
        if (idx == k) {
            rotate();
            return;
        }

        for (int i = 0; i < k; i++) {
            if (!visited[i]) {
                visited[i] = true;
                arr[idx] = i; // 회전 연산의 순서를 위한 배열
                permutation(idx + 1);
                visited[i] = false;
            }
        }
    }

    private static void rotate() {
        int[][] tmp = copyMap();

        for (int i = 0; i < k; i++) {
            int r = rotation[arr[i]][0];
            int c = rotation[arr[i]][1];
            int S = rotation[arr[i]][2];

            for (int s = 1; s <= S; s++) { // 내부에 있는 사각형의 회전
                // 위쪽
                int upTmp = tmp[r - s][c + s];
                for (int y = c + s; y > c - s; y--) {
                    tmp[r - s][y] = tmp[r - s][y - 1];
                }

                // 오른쪽
                int rightTmp = tmp[r + s][c + s];
                for (int x = r + s; x > r - s; x--) {
                    tmp[x][c + s] = tmp[x - 1][c + s];
                }
                tmp[r - s + 1][c + s] = upTmp;

                //아래
                int leftTmp = tmp[r + s][c - s];
                for (int y = c - s; y < c + s; y++) {
                    tmp[r + s][y] = tmp[r + s][y + 1];
                }
                tmp[r + s][c + s - 1] = rightTmp;

                //왼쪽
                for (int x = r - s; x < r + s; x++) {
                    tmp[x][c - s] = tmp[x + 1][c - s];
                }
                tmp[r + s - 1][c - s] = leftTmp;
            }
        }

        getResult(tmp);
    }

    private static int[][] copyMap() {
        int[][] tmp = new int[n][m];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                tmp[i][j] = arrayMap[i][j];
            }
        }
        
        return tmp;
    }

    private static void getResult(int[][] tmp) {

        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = 0; j < m; j++) {
                sum += tmp[i][j];
            }

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