[백준] 17406번 : 배열 돌리기 4 - 자바(Java)

Problem 🔒

문제

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의 값의 최솟값을 출력한다.

제한

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

---

Approach ⭕

1. 회전 연산 순서 정하기(DFS 메서드)
   • 각 회전 연산의 순서에 따라 최종 결과가 달라지므로, 모든 순서를 고려해야한다.
   • DFS 함수를 통해 회전 연산의 모든 순열을 생성했다.
2. 깊은 복사
   • 회전 연산 순서가 정해졌으면 copyMap 배열에 map 배열을 깊은 복사했다.
   • 깊은 복사를 한 이유는 원본 배열을 수정하지 않고, 다양한 회전 연산 순서를 적용하기 위해서이다.
3. 회전(ROT 메서드)
   
   • 해당 회전 연산 값에 따라 회전의 범위를 계산해, 바깥쪽에서 안쪽으로 회전을 진행했다.
   • 방향벡터 dr, dc를 활용하여 시계 방향으로 이동하며 값을 교체했다.
4. 행 합계 계산
   • 회전이 완료된 copyMap에서 각 행의 합계를 계산하고, 최소 합계 값을 갱신했다.

---

Solution 💡

import java.util.Arrays;
import java.util.Scanner;

public class 배열돌리기4 {
    static int N, M, K;
    static int[][] map;
    static int[][] rotation;
    static int[] order; // 순서 담을 배열
    static boolean[] visit; // 방문 배열
    static int[][] copyMap; // map 깊은 복사
    static int[] dr = {0, 1, 0, -1};
    static int[] dc = {1, 0, -1, 0};
    static int res = 54321;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        K = sc.nextInt();
        map = new int[N][M];
        rotation = new int[K][3];

        order = new int[K];
        visit = new boolean[K];

        // map 입력
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                map[i][j] = sc.nextInt();
            }
        }
        // 회전 입력
        for(int i=0; i<K; i++){
            for(int j=0; j<3; j++){
                rotation[i][j] = sc.nextInt();
            }
        }

        // 회전 연산 순서 뽑기
        DFS(0);

        // 최소값 출력
        System.out.println(res);

    }

    static void Print(int[][] graph){
        for(int[] row : graph){
            for(int c : row){
                System.out.print(c);
            }
            System.out.println();
        }
    }

    static void DFS(int depth){
        if(depth == K){
            // map 깊은 복사
            copyMap = new int[N][M];
            for(int i=0; i<N; i++){
                for(int j=0; j<M; j++){
                    copyMap[i][j] = map[i][j];
                }
            }

            // 회전 연산 순서 정했다면 회전 함수 실행
            ROT(order);

            // 행 합계
            for(int[] row : copyMap){
                int sum = 0;
                for(int c : row){
                    sum += c;
                }
                if(sum < res){
                    res = sum;
                }
            }
        }
        for(int i=0; i<K; i++){
            if(!visit[i]){
                visit[i] = true;
                order[depth] = i;
                DFS(depth+1);
                visit[i] = false;
            }
        }
    }

    static void ROT(int[] ord){
        for(int o : ord){
            // 왼쪽 위, 오른쪽 아래 좌표 구하기
            int startRow = rotation[o][0] - rotation[o][2] - 1;
            int startCol = rotation[o][1] - rotation[o][2] - 1;
            int endRow = rotation[o][0] + rotation[o][2] - 1;
            int endCol = rotation[o][1] + rotation[o][2] - 1;

            int n = 0;
            while(true){
                int startR = startRow + n;
                int startC = startCol + n;
                int endR = endRow - n;
                int endC = endCol - n;

                if(startR == endR && startC == endC) break;

                int tmpB = copyMap[startR][startC];
                int tmpA;
                int nr = startR;
                int nc = startC;

                TDout:
                for(int d=0; d<4; d++){
                    boolean flag = true;

                    while(flag){
                        nr += dr[d];
                        nc += dc[d];

                        if(nr>=startR && nc>=startC && nr<=endR && nc<=endC){
                            tmpA = copyMap[nr][nc];
                            copyMap[nr][nc] = tmpB;
                            tmpB = tmpA;

                            if(nr == startR && nc == startC) break TDout;
                        }else{
                            flag = false;
                            nr -= dr[d];
                            nc -= dc[d];
                        }
                    }
                }// TDout
                n++;
            }// 시계방향 회전 끝
        }
    }
}