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

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

 

풀이과정

크기가 N X M 배열이 있을 때 각 행에 있는 모든 수의 합이 가장 최소일 때를 구하는 문제이다.

 

회전 연산이 세 정수 (r, c, s)로 주어지고

가장 왼쪽 윗 칸 (r - s. c - s)

가장 오른쪽 아래 칸 (r + s, c + s)

정사각형을 시계 방향으로 한 칸씩 돌리면 된다.

 

예를 들어, 배열 A의 크기가 6×6이고, 회전 연산이 (3, 4, 2)인 경우에는 아래 그림과 같이 회전하게 된다.

 

r = 3 c = 4 s = 2

가장 왼쪽 윗 칸 (3 - 2, 4 - 2) = (1, 2)

가장 오른쪽 아래 칸 (3 + 2, 4 + 2) = (5, 6)

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]

 

배열과 사용 가능한 회전 연산이 주어졌을 때 최솟값을 구하면 되는데,

회전 연산은 모두 한 번씩 사용해야 된다는 조건이 있기 때문에

순열을 구현하기 위한 백트래킹을 떠올릴 수 있었다.

 

각 회전 연산의 순열에 따라 백트래킹을 돌리고

기저조건일 경우에 rotate를 다 돌리고, 각 행에 있는 모든 수의 합을 업데이트해주면 된다. 

 

---

여기서 rotate의 구현이 헷갈려서 정리해보자면,

 

먼저 시작점과 끝점을 (sx, sy) (ex, ey)로 둔다.

그 다음 s개만큼의 정사각형이 있을 것이다.

 

그래서 각 정사각형에 대해 회전을 하는 반복문을 지정해두고

시작점 sx, sy에 layer를 더해서 재할당한다.

시작점은 회전하다 보면 소실되기 때문에 temp라는 곳에 미리 담아둔다.

 

- 왼쪽 열 위로 이동

- 아래쪽 행 왼쪽으로 이동

- 오른쪽 열 아래로 이동

- 위쪽 행 오른쪽으로 이동

 

4번 이동하고 나서 첫 시작점 + 1 (시계방향이라서 행 이동) 한 곳에 temp를 할당해준다.

 

 

정답 코드

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

class Main
{
	
    static int N, M, K;
    static int r, c, s;
    static int[][] arr;
    static int[][] newArr;

    static Rotate[] rotate;
    static boolean[] visited;
    static int res = Integer.MAX_VALUE;

    static List<Rotate> rotatenewArr = new ArrayList<>();

    static class Rotate{
        private int r;
        private int c;
        private int s;

        public Rotate(int r, int c, int s) {
            this.r = r;
            this.c = c;
            this.s = s;
        }
    }

    static int[][] copyArr() {
        newArr = new int[N + 1][M + 1];

        for(int i = 1; i <= N; i++) {
            for(int j = 1; j <= M; j++) {
                newArr[i][j] = arr[i][j];
            }
        }
        return newArr;
    }

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

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

        // 입력
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        arr = new int[N + 1][M + 1];
        for(int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 1; j <= M; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        rotate = new Rotate[K];
        for(int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());

            r = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());
            s = Integer.parseInt(st.nextToken());

            rotate[i] = new Rotate(r, c, s);
        }

        // 회전 백트래킹
        visited = new boolean[K];
        dfs(0);

        // 출력
        System.out.println(res);
    }

    static void dfs(int depth) {
        if (depth == K) {   
            int[][] newArr = copyArr();
            // 회전 순열
            for(int k = 0; k < rotatenewArr.size(); k++) {
                Rotate rotate = rotatenewArr.get(k);

                r = rotate.r;
                c = rotate.c;
                s = rotate.s;

                rotate(r, c, s);
            }

            // 각 행 최솟값 업데이트
            for(int i = 1; i <= N; i++) {
                int sum = 0;
                for(int j = 1; j <= M; j++) {
                    sum += newArr[i][j];
                }
                res = Math.min(res, sum);
            }
            return;
        }

        for(int i = 0; i < K; i++) {
            if (!visited[i]) {
                visited[i] = true;
                rotatenewArr.add(rotate[i]);
                dfs(depth + 1);
                visited[i] = false;
                rotatenewArr.remove(rotatenewArr.size() - 1);
            }
        }
    }

    static void rotate(int r, int c, int s) {
        int sx = r - s; // 상단 시작 x
        int sy = c - s; // 좌측 시작 y
        int ex = r + s; // 하단 끝 x
        int ey = c + s; // 우측 끝 y

        // 각 레이어에 대해 회전
        for (int layer = 0; layer < s; layer++) {
            int x = sx + layer;
            int y = sy + layer;

            int temp = newArr[x][y];

            // 왼쪽 열 위로 이동
            for (int i = x; i < ex - layer; i++) {
                newArr[i][y] = newArr[i + 1][y];
            }

            // 아래쪽 행 왼쪽으로 이동
            for (int i = y; i < ey - layer; i++) {
                newArr[ex - layer][i] = newArr[ex - layer][i + 1];
            }

            // 오른쪽 열 아래로 이동
            for (int i = ex - layer; i > x; i--) {
                newArr[i][ey - layer] = newArr[i - 1][ey - layer];
            }

            // 위쪽 행 오른쪽으로 이동
            for (int i = ey - layer; i > y + 1; i--) {
                newArr[x][i] = newArr[x][i - 1];
            }

            newArr[x][y + 1] = temp;
        }
    }

}